問 題
正規表現 a(a*)(b*) に対応する有限オートマトン、すなわち a(a*)(b*) が表す記号列を全て受理し、それ以外を受理しない有限オートマトンの状態遷移図として最も妥当なのはどれか。
ただし図において太い矢印が示す状態は初期状態を二重丸で表された状態は受理状態をそれぞれ表す。また a* は a を０回以上繰り返してできる有限な長さの記号列を表す。すなわち正規表現 a(a*)(b*) は１個以上の a の記号列の後に０個以上の b の記号列を結合してできる有限な長さの記号列 (例えばa,aa,ab,aab,aaabbbbb) の全てを表している。
正解 (5)
解 説
選択肢 における左側を 状態 1、右側を 状態 2 とします。
a,b,aa,ab,bb,aab などを考えていきます。
a は「受理」しなければいけません。選択肢 2,4 は 状態 1 のままです。受理しません。よって、選択肢 2,4 は誤りです。
b は受理してはいけません。これは 1,3,5 OKです。
aa は受理しなければいけません。 OK
ab は受理しなければなりません。 OK
bb は受理してはいけません。 OK
うーん、なんかうまくいかないなぁと不安になってくる所ですね。aaa は明らかに aa と変わらないので、aba を考えます。これは受理してはいけません。ところが選択肢 1,3 は受理してしまいます。よって、選択肢 1,3 は誤りです。
以上より、正解は 5 です。
コメント