makenowjust-labs/blog

正規表現マッチングの実装手法の1つとしてPike VMと呼ばれるものがあります。 これはGo言語の正規表現実装やRustのregex crateで使われている手法であり、正規表現$r$と入力文字列$w$に対して$O(|r| \times |w|)$の計算量でマッチングができるのが特徴です。

Earley法はJay Earleyの提案した文脈自由文法 (CFG) の構文解析手法の1つです。 すべてのCFGを構文解析できる手法で最悪計算量は$O({|w|}^3)$ですが、無曖昧であれば$O({|w|}^2)$で、決定的であれば$O({|w|})$で構文解析ができます。

実装してみると分かりますが、Pike VMとEarley法には類似している点があり、Earley法をPike VMの発展系のように考えることができます。 この記事ではPike VMとEarley法のRubyでの実装を通じて、それらの関係を解説します。

想定読者: 形式言語や構文解析についての基本的な知識がある (NFAやCFGなどを知っている) ことを想定しています。

Automata Learning とは、未知の (ブラックボックス) システムに対する入力とその出力から、システムの振舞いを有限状態オートマトンとして再現する手法です。 これは、仕様が形式化されていないシステムに対して形式的な手法を適用するための足掛りになるなど、近年重要な技術となっています。

Angluin による$L\ast$は Automata Learning のアルゴリズムの中でも最も代表的な存在です。 $L\ast$は未知の正規言語を教師を使って学習するアルゴリズムで、多くの Automata Learning の基礎となっています。

この記事では$L\ast$の、その原理やアルゴリズムの詳細について解説します。

前回の記事では DFA 最小化アルゴリズムとして Brzozowski のアルゴリズムを解説しました。 今回は、別の最小化アルゴリズムとして Hopcroft のアルゴリズムについて解説します。

"Introduction to Automata Theory, Languages, and Computation" (日本語訳『オートマトン 言語理論 計算論』) の著者の一人として知られる John Hopcroft が 1971 年に発表したアルゴリズムです。 実装を工夫することで最悪計算量は DFA の状態数 $n$ に対して $O(n \log n)$ となることが知られています。 しかし、正当さがやや直感的でないことから、オートマトン理論の教科書や講義などで触れられる機会は少ないように思います。

この記事では、Hopcroft のアルゴリズムの実装に加えて、その正しさの証明や計算量の解析を行います。

$A$ を言語 $L$ を受理する DFA とすると、$D(R(D(R(A))))$ は言語 $L$ を受理する最小 DFA となります。 ここで $D(A)$ というのは部分集合構成法による決定化の処理で、$R(A)$ は DFA の各遷移と初期状態・受理状態を反対にして NFA を求める処理を表します。 この 2 回のリバースと決定化を行う DFA の最小化アルゴリズムは Brozozowski のアルゴリズム として知られています。 Brzozowski 微分などで知られる Janusz Brzozowski が 1960 年代に発表したアルゴリズムです。

以前 Qiita でこのアルゴリズムでどうして DFA の最小化が行なえるのかを説明したのですが(Brzozowski のアルゴリズム - なぜ DFA を 2 回反転すると最小化できるのか )、これによって構成される DFA がどのようなものなのかは説明していませんでした。 今回のこの記事では、Brozozowski のアルゴリズムで求まる最小 DFA がどのようなものなのかを別の角度から少し解説したいと思います。