
正規表現と有限オートマトン
用語の意味
正規表現は文字列のパターンを表します。基本的な記法で | は選択、* は直前の要素の0回以上の繰返しです。有限オートマトンは有限個の状態と、入力に応じた遷移で文字列を判定します。
使いどころと問題の見方
状態遷移図では開始状態から入力を1文字ずつたどり、すべて消費した時点で受理状態にいるかを確認します。例えば直前の文字が1かどうかを2状態で保持すれば、末尾が1のビット列を判定できます。一般のプログラミング言語の正規表現には、基本的な正規言語の範囲を超える拡張もあります。
確認問題【オリジナル】
式 ab* が文字列全体に一致するものはどれですか。
ア.b
イ.ba
ウ.aba
エ.a
正解と理由
正解はエです。bが0回でもよいためaは一致します。aの後にb以外は置けません。