問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}、q0=0∈Q、L={0,3}

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

Post filed under 自習.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です