状態 p（開始状態）、q、r（受理状態）からなる DFA の遷移が、p では a で q・b で p、q では a で q・b で r、r では a で q・b で p である。この DFA が受理する文字列はどれか。

解説

正解は「babab」です。babab を読むと、p→p（b）→q（a）→r（b）→q（a）→r（b）と遷移し、受理状態 r で終わるので受理されます。この DFA は、直前に a を読んだら q、ab と読んだ直後なら r に入るように作られており、ab で終わる文字列を受理します。「abba」は q→r→p→q と進み、q で終わるので受理されません。「aabb」は q→q→r→p と進み、最後の b で r から p に戻るので受理されません。「bba」は p→p→q で終わり、受理されません。いずれも ab で終わっていない点が共通しています。