応用数学 (全39問中28問目)

No.28

次の有限オートマトンで受理する文全体を正規表現で表したものはどれか。
08.gif/image-size:361×67
正規表現に用いるメタ記号は,次のとおりとする。
 r1|r2: 正規表現r1又は正規表現r2
 (r)*: 正規表現rの0回以上の繰返し

分類

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

正解

解説

設問の有限オートマトンは初期状態で1が入力されると受理状態へ遷移するので文の最後は1になります。
受理する過程ですが、
  • 初期状態で0を繰り返して1で受理状態に遷移する
  • 初期状態と受理状態を1→0で繰り返して1で受理状態に遷移する
の2種類があります。

0または10を繰り返した後、1で終了するので「(0 | 10)*1」になります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop