有限オートマトン2-1.定義 その4

 解答3
 ΣaaaΣの部分はこんな感じ(主要部のみ)になるはずだ。

 aをbに変えて同じ形のものを作れば、ΣbbbΣの流れができる。初期状態と受理状態を同じところに合わせるとこんな感じ。

 ここで、aaaやbbbの途中で他の文字が来た場合は、単にエラーにすればいいのかと思ったが、違う。
 たとえば、「***a***aaa***」「***aab***aaa***」「***bbaaa***」などという語もΣaaaΣの元だからだ。
 a…を受け取って左の流れに入った後でも、スタートに戻ったり、右の流れにレーンチェンジすることを考えなければならない。逆も同様。したがって、

 こうなると考えた。
 Q={0,1,2,3,4,5}としたが、どうもしっくりこない。受理する言語かどうかの判定は、「連続で出てきたaまたはbの数」を記憶すればいいわけだから、aの連続を1,2,3、bの連続を1,2,3と数えたいが…。これは単なるラベルと考えていいんだろうか?


Want to Leave a Reply?