正規表現に用いるメタ記号は、次のとおりとする。
r1 | r2 : 正規表現r1又は正規表現r2
(r )* : 正規表現r の0回以上繰り返し
次の有限オートマトンで受理する文全体を正規表現で表したものはどれか。
正規表現に用いるメタ記号は、次のとおりとする。
r1 | r2 : 正規表現r1又は正規表現r2
(r )* : 正規表現r の0回以上繰り返し
| ア | (010)* 1 |
| イ | (01 | 101)* |
| ウ | (0 | 10)* 1 |
| エ | (1 | 01)* |
答え ウ
【解説】
問題の有限オートマトンで受理状態になるための入力パターンには“1”、“01”、“001”、“101”、“0101”、“01001”などがある。また、途中で“11”の入力パターンがあるとが受理状態にはならない。
| ア | この表現では受理状態になるための“01”の入力パターンが発生しない。 |
| イ | 入力パターンとして“01101”があり、これは“11”があるので受理状態にならない。 |
| ウ | 入力パターンとして、“01”、“101”など、受理状態になるすべてを表現できる。 |
| エ | 入力パターンとして“011”があり、これは“11”があるので受理状態にならない。 |
【キーワード】
・有限オートマトン
戻る
一覧へ
次へ