平成２７年　技術士第一次試験問題　Ⅲ－２８：非決定性有限オートマトン

平成２７年度　技術士第一次試験問題【専門科目】

下図の非決定性有限オートマトンが受理するすべての文字列を表す正規表現はどれか。ただし、入力される文字列のアルファベットは {a,b}, εは空列とし、正規表現において、r*は r の0回以上の繰り返し、(r1|r2) は選択を表す。

　

①　(a|b)*

②　(a|ba)*

③　a*|(ba)*

④　a*ba(ba)*

⑤　a*|((ba)(ba)*)

②

①　正規表現では、aaa bbbなどが表現できるが、オートマトンでは、bbbを受理しない。

②　正しい。

③　オートマトンでは、aba が受理できるが、これを表現できない。

④　オートマトンでは、aaが受理できるが、これを表現できない。

⑤　ba のあとに(ba)* がなかった場合、初期状態に戻ってしまう。