HOME»ソフトウェア開発技術者平成19年秋期»午前問8
ソフトウェア開発技術者平成19年秋期 午前問8
問8
次の有限オートマトンで受理する文全体を正規表現で表したものはどれか。
正規表現に用いるメタ記号は，次のとおりとする。
r1｜r2：正規表現r1又は正規表現r2
(r)*：正規表現rの0回以上の繰返し
r1｜r2：正規表現r1又は正規表現r2
(r)*：正規表現rの0回以上の繰返し
- (010)*1
- (01 | 101)*
- (0 | 10)*1
- (1 | 01)*
分類
テクノロジ系 » 基礎理論 » 応用数学
正解
ウ
解説
設問の有限オートマトンは初期状態で1が入力されると受理状態へ遷移するので文の最後は1になります。受理する過程ですが以下の2つのパターンがあります。
他の正規表現は少なくとも、初期状態で0を繰り返した後に1で受理する 000...01 というパターンにマッチしないので誤りと判断できます。
- 初期状態で0を繰り返して1で受理状態に遷移する
- 初期状態と受理状態を1→0で繰り返して1で受理状態に遷移する
他の正規表現は少なくとも、初期状態で0を繰り返した後に1で受理する 000...01 というパターンにマッチしないので誤りと判断できます。