先週のエントリー「この機会にマスターしようぜ、正規表現、構文図、オートマトン」において、正規表現とオートマトンの理屈は説明しました。んじゃ、適当な正規表現に対応するオートマトンを作ってみましょう。 非決定性オートマトンはめんどくさいので決定性オートマトンにします。正規表現から作ったオートマトンが非決定性になってしまったときは、がんばって決定性オートマトンに変形するかあきらめるかしてください。 例題となる正規表現とオートマトンは、「Erlang実験室:状態遷移を書くのはこんなに簡単」で使ったものをそのまま流用します。 正規表現: (a, a?, b*, c) 図と表のなかで、EOSは End Of String のマーカー、◎は終状態です 遷移表: 0から3までの各状態について、入力ごとの遷移先は次の通り。×はエラーです。 状態 文字a 文字b 文字c EOS その他 0 1 × × × ×
![正規表現とオートマトン:なんだ簡単じゃん、JavaScriptによる実装 - 檜山正幸のキマイラ飼育記 (はてなBlog)](https://cdn-ak-scissors.b.st-hatena.com/image/square/d2edc9d12c93135c55920bf080cf578d5a34eae4/height=288;version=1;width=512/http%3A%2F%2Fwww.chimaira.org%2Fimg2%2Fautom-states.gif)