技術士第一次試験専門科目情報工学部門 H27 問題28

Question

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

①

(a|b)*

②

(a|ba)*

③

a*|(ba)*

④

a*ba(ba)*

⑤

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

自信なし

Accepted Answer

図の遷移により、初期状態から受理状態へ空列で到達でき、途中の上側経路で、下側経路でを1単位として受理状態へ進める。受理状態から初期状態へで戻れるため、この又はの単位を0回以上繰り返せる。正規表現はとなり、正解は②である。

技術士第一次試験専門科目情報工学部門 H27