HOME»テクノロジ系»応用数学»No.44

応用数学　(全55問中44問目)

No.44

次の有限オートマトンで受理する文全体を正規表現で表したものはどれか。
08.png/image-size:361×67
正規表現に用いるメタ記号は，次のとおりとする。
　r1｜r2：正規表現r1又は正規表現r2
　(r)*：正規表現rの0回以上の繰返し
出典：平成19年秋期　問8
  • (010)*1
  • (01 | 101)*
  • (0 | 10)*1
  • (1 | 01)*

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

ウ

解説

設問の有限オートマトンは初期状態で1が入力されると受理状態へ遷移するので文の最後は1になります。受理する過程ですが以下の2つのパターンがあります。
  • 初期状態で0を繰り返して1で受理状態に遷移する
  • 初期状態と受理状態を1→0で繰り返して1で受理状態に遷移する
0または10を0回以上繰り返した後に1で終了する文字列なので、「(0 | 10)*1」が適切な正規表現です。

他の正規表現は少なくとも、初期状態で0を繰り返した後に1で受理する 000...01 というパターンにマッチしないので誤りと判断できます。
© 2010-2024　応用情報技術者試験ドットコム　All Rights Reserved.
▲
Pagetop