正規表現エンジンを作ろう （5）

はじめに こんにちは。hirataraです。 前回までの連載で、正規表現からNFAを構築する部分までを作成しました。今回は、NFAをDFAに変換する部分集合構成法を解説し、今まで作った部品を組み合わせて正規表現エンジンを完成させます。 対象読者 正規表現をもっと知りたい方 情報科学分野に興味がある方 正規表現エンジンを実装する必要がある方 部分集合構成法 NFAをDFAに変換するには、部分集合構成法（subset construction）と呼ばれる方法を利用します。 第1回で説明した通り、NFAは1つの文字の入力によって一意に状態が決まらないのが特徴でした。'a'を入力すると、1になるかもしれないし、2になるかもしれません。そして、NFAのシミュレート方法には、バックトラックを利用する深さ優先の方法と、もう一つ、幅優先の方法があることも紹介しました。幅優先の動作では、入力による遷移の全て