問2.2 次の各言語を受理する有限オートマトンを構成せよ。
- {aa,bb}*
- {aa}*{bb}*
- Σ*aaaΣ*∪Σ*bbbΣ*
解答
1.
言語の仕様(定義)を確認しておこう。 {aa,bb}*={ε,aa,bb,aabb,aaaabb,bbaa,…}であって、abとかbabのように同じ文字が2文字連続ではないものは含まないわけだ。したがって2文字目が1文字目と同じだったら受理状態になる。
丁寧に(かつ題意を汲んで)考えると、アルファベットΣ={a,b} 上のすべての語の集合、
Σ*={ε,aa,bb,ab,ba,aba,…} の部分集合
Σ* ⊇ {aa,bb}*
…を受理するわけだから、受理しない語(ab,ba,aba,…)も渡される事を考えなければ。
はて、状態の集合はどう決めればいいんだろう。「受理するかどうか」だけしか情報がないなら、yes/noとか0/1でいいような気もするが。ああ、でも1文字目がaだったときとbだったときで行先は別の状態としなければいけないから、識別のために自然数がいいだろうな。
Q={0,1,2,3}ということで。これで完成だ。たぶん。
2.
同様に考え、Q={0,1,2,3,4}、q0=0∈Q、L={0,3}
3はまた今度。同じように考えればできそうだ。