先週のエントリー「この機会にマスターしようぜ、正規表現、構文図、オートマトン」において、正規表現とオートマトンの理屈は説明しました。んじゃ、適当な正規表現に対応するオートマトンを作ってみましょう。 非決定性オートマトンはめんどくさいので決定性オートマトンにします。正規表現から作ったオートマトンが非決定性になってしまったときは、がんばって決定性オートマトンに変形するかあきらめるかしてください。 例題となる正規表現とオートマトンは、「Erlang実験室:状態遷移を書くのはこんなに簡単」で使ったものをそのまま流用します。 正規表現: (a, a?, b*, c) 図と表のなかで、EOSは End Of String のマーカー、◎は終状態です 遷移表: 0から3までの各状態について、入力ごとの遷移先は次の通り。×はエラーです。 状態 文字a 文字b 文字c EOS その他 0 1 × × × ×