直積オートマトンの説明で、上の有限オートマトンともう1つ0,1が偶数個あるオートマトンが合わさってたんですが、上のオートマトンがどんな言語を受理するのかが授業中にわからなかったっすorz

はじめは1？

1か0は3連続しない？

いろいろ考えましたけど、書いて表現するのが難しかったので先生に聞いてみることにしたら

「なんでしょうね？このオートマトンが受理するのは」

先生、そりゃないですよorz

どうやら以前配布した資料から拝借したらしいので、探してみたらありましたよ！

L = { x | x ∈ {0 , 1}^* | ∀y : yは任意のxのprefix , 0 ≦ #₁(y) - #₀(y) ≦ 2 }

まぁ、自分の言いたかったことは表現されているのでこれで正しいんでしょう。

こんなの思いつかなかったよ。

「直前までの記号列のうち1の個数nと0の個数mが0≦n-m≦2を満たす」

とかしか思いつかなかった。近いところまでは行ったんだけどね～

勉強というよりは、パズルを解いているような感覚に近い授業です

プレフィックス