正規表現からオートマトンへの変換

例

アルゴリズムそのものを説明する前に、何をしたいのかを例で見てみましょう。正規表現 a(b|c)x^∗ を考えます。この正規表現が表す言語を言葉で説明すると、文字「a」で始まり、次に文字「b」か「c」のどちらかが来て、そのあとに文字「x」が任意の個数続く語の集合です。この言語を受理するオートマトンはつくれるでしょうか。もちろんつくれます。次のとおりです。

このオートマトンが同じ言語を受理することは明らかです。そこで、どんな正規表現についても、その言語を受理するオートマトンが存在するのかという疑問がわきます。答えは「はい」です。

正規表現をオートマトンに変換するアルゴリズム

入力として正規表現 R が与えられているとします。正規表現の記事で見たように、正規表現の形は全部で6通りです。そこで、次の6つの場合に分けます。

R = a（ただし a ∈ Σ は記号）。つまり、正規表現が、扱っているアルファベット Σ の記号1つだけからなる場合です。記号 a を1つだけ受理するオートマトンは、次のようになります。
R = ϵ、つまり空語の場合です。空語を受理するオートマトンは、次のようになります。
R = ∅、つまり空の言語を表す正規表現の場合です。このような言語を受理するオートマトンは次のとおりです。
R = R₁ ∪ R₂（ただし R₁, R₂ は正規表現）。正規言語の和集合がまた正規言語であることと、その言語を受理するオートマトンをつくれることは、すでにわかっています。言いかえると、正規表現 R₁ と R₂ が表す言語を受理するオートマトンがあると仮定し、それらを使って、正規表現 R₁ ∪ R₂ が表す言語を受理するオートマトンをつくります。例えば R₁ = a、R₂ = ϵ のとき、この手順で次のオートマトンが得られます。
R = R₁ ∘ R₂（ただし R₁, R₂ は正規表現）。前の場合と同じです。正規言語の連接は正規言語なので、その言語を受理するオートマトンをつくれます。例えば R₁ = a、R₂ = b のとき、連接は次のようになります。
$R = (R_{1}^{*})$ （ただし R₁ は正規表現）。これも、正規言語のクリーネ閉包が正規言語であることはわかっています。例えば R = a^∗ のとき、オートマトンは次のようになります。

これらの場合を順に当てはめていけば、正規表現全体を有限オートマトンに変換できます。

変換の総合的な例

正規表現 (a|bc)^∗ を変換してみましょう。順に次のオートマトンが得られます。

この最終的なオートマトンは、正規表現 (a|bc)^∗ が表す言語を受理します。もちろん、このオートマトンはひどく複雑で、同じ言語を受理するもっとずっと簡単なオートマトンがあるはずです。簡単にするには、NFA から DFA への変換のアルゴリズムを使い、続けてオートマトンの最小化を行います。

参考文献

章: 正規表現, 正規表現からオートマトンへの変換, 一般化非決定性有限オートマトン, オートマトンから正規表現への変換

« 前へ: 正規表現

次へ: 一般化非決定性有限オートマトン »