分野別過去問題テクノロジ系　応用数学 No.44

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

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

正規表現に用いるメタ記号は，次のとおりとする。
　r₁｜r₂：正規表現r₁又は正規表現r₂
　(r)^*：正規表現rの0回以上の繰返し

出典：平成19年秋期　問 8

正解　ウ問題へ

分野：テクノロジ系
中分類：基礎理論
小分類：応用数学

解説

設問の有限オートマトンは初期状態で1が入力されると受理状態へ遷移するので文の最後は1になります。受理する過程ですが以下の2つのパターンがあります。

0または10を0回以上繰り返した後に1で終了する文字列なので、「(0 | 10)^*1」が適切な正規表現です。

他の正規表現は少なくとも、初期状態で0を繰り返した後に1で受理する 000...01 というパターンにマッチしないので誤りと判断できます。