解答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と数えたいが…。これは単なるラベルと考えていいんだろうか?