正規表現とオートマトン

正規表現とオートマトン 正規表現は、文字列のパターンマッチングを行うための汎用的な文法です。さまざまなプログラミング言語やコマンドラインツールなどで利用されています。 正規表現の理論的な背景として、オートマトンという概念があります。オートマトンは計算機科学の分野で研究されており、計算理論の教科書によく取り上げられています。ただ、いきなり教科書でオートマトンの説明を読んでも、わりと数学的な話で、プログラミングで扱っている正規表現のイメージとは少しギャップがあります。そこで本記事では、簡単な正規表現のマッチング処理のコードを書いてみて、オートマトンの概念をつかんでみます。 なお、コードを記述するプログラミング言語はなんでもよいのですが、本記事ではRustを使います。難しい文法は使わないので、Rustを知らなくても問題ありません。 正規表現のマッチング処理の素朴な実装 具体例として、正規表現 a