問2.2　次の各言語を受理する有限オートマトンを構成せよ。

1. {aa,bb}^＊
2. {aa}^＊{bb}^＊
3. Σ^＊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}、q₀＝0∈Q、L＝{0,3}

3はまた今度。同じように考えればできそうだ。