次の有限オートマトンで受理する文全体を正規表現で表したものはどれか。
正規表現に用いるメタ記号は、次のとおりとする。
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”があるので受理状態にならない。 |
【キーワード】
・有限オートマトン
【キーワードの解説】
- 有限オートマトン
システムの動作を有限個の状態と、有限個の遷移で表したもの。状態遷移図の一種です。
通常、有限オートマトンには開始の状態と最終的な状態があります。
もっと、「有限オートマトン」について調べてみよう。
戻る
一覧へ
次へ
|