平成19年 秋期 ソフトウェア開発技術者 午前 問8

次の有限オートマトンで受理する文全体を正規表現で表したものはどれか。


 正規表現に用いるメタ記号は、次のとおりとする。
  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”があるので受理状態にならない。


キーワード
・有限オートマトン

キーワードの解説
  • 有限オートマトン
    システムの動作を有限個の状態と、有限個の遷移で表したもの。状態遷移図の一種です。
    通常、有限オートマトンには開始の状態と最終的な状態があります。

もっと、「有限オートマトン」について調べてみよう。

戻る 一覧へ 次へ