正規言語の和集合

2つの正規言語 L₁, L₂ を考えます。その和集合 L = L₁ ∪ L₂ も正規言語であることを証明します。

決定性オートマトンを使う方法

考え方

2つの正規言語 L₁ と L₂ があり、その和集合 L₁ ∪ L₂ もまた正規言語であることを証明したいとします。L₁ と L₂ は正規言語なので、有限オートマトン A₁ と A₂ が存在し、それぞれ言語 L₁ と L₂ を受理します。つまり、L(A₁) = L₁ と L(A₂) = L₂ が成り立ちます。ここで、有限オートマトン A をつくって言語 L₁ ∪ L₂ を受理させれば、言語 L₁ ∪ L₂ が正規言語であることを証明できます。

どうすればよいでしょうか。手元には、それぞれの言語を受理する有限オートマトン A₁ と A₂ があります。語 w が言語 L₁ ∪ L₂ に属するのは、オートマトン A₁ と A₂ の少なくとも一方がこの語を受理するとき、またそのときに限ります。

例えば、オートマトン A は入力 w に対して、オートマトン A₁ に入力 w を与えたときの計算をシミュレートするように動くことが考えられます。A₁ が語 w を受理すれば、語 w は A にも受理されます。A₁ が語 w を受理しなければ、A はさらに、A₂ に入力 w を与えたときの計算をシミュレートしてみます。A₂ が語 w を受理すれば、A も語 w を受理します。そうでなければ、受理しません。

あとは、オートマトン A がほかのオートマトンの計算を「シミュレートする」とはどういうことかを形式化するだけです。

形式化

2つの正規言語 L₁ と L₂ があり、それぞれ次の有限オートマトンに受理されるとします。

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

有限オートマトン A = ⟨Q, Σ, δ, q, F⟩ をつくり、言語 L = L₁ ∪ L₂ を受理するようにします。2つのオートマトン A₁, A₂ をシミュレートするという考え方を使います。入力が語 w = w₁w₂… w_n だとして、オートマトン A₁ と A₂ の語 w に対する動きを同時にシミュレートしてみましょう。オートマトン A₁ の初期様相は ⟨q₁, w₁w₂… w_n⟩、A₂ の初期様相は ⟨q₂, w₁w₂… w_n⟩ です。それぞれのオートマトンで計算を1ステップ行うと、様相 ⟨δ₁(q₁, w₁), w₂… w_n⟩ と ⟨δ₂(q₂, w₁), w₂… w_n⟩ に移ります。

これらの様相は1つ目の成分だけが異なり、2つ目の成分、つまり語のまだ読んでいない部分はいつも同じです。そのため、シミュレートするあいだ、2つのオートマトンの様相を2つとも保持する必要はなく、⟨⟨q_i, q_j⟩, w_l… w_n⟩ の形の様相を1つ保持するだけで済みます。ここで q_i ∈ Q₁、q_j ∈ Q₂ です。言いかえると、これからつくるオートマトン A の初期様相は ⟨⟨q₁, q₂⟩, w⟩ です。組 ⟨q₁, q₂⟩ の1つ目の成分はオートマトン A₁ が今いる状態を、2つ目の成分はオートマトン A₂ が今いる状態を表します。

そこで、つくるオートマトン A の状態の集合は Q = Q₁ × Q₂ と書けます。もとの2つのオートマトンの状態の集合の直積です。さらに、オートマトン A の初期状態を ⟨q₁, q₂⟩ とします。そして、オートマトン A₁ が記号 w₁ で状態 q_i に移り、オートマトン A₂ が記号 w₁ で状態 q_j に移るなら、オートマトン A は記号 w₁ で状態 ⟨q_i, q_j⟩ に移るようにします。

遷移関数 δ は次のように書けます（ここでは、今いる状態が q_i と q_j であるとします）。

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

残りは細かい点だけです。アルファベットは Σ= Σ₁ ∪ Σ₂ とします。初期状態は q = ⟨q₁, q₂⟩ です。受理状態は、組 ⟨q_i, q_j⟩ のうち、q_i ∈ F₁ または q_j ∈ F₂ を満たすものすべてです。

手順の例

2つのオートマトンを考えます。1つ目はオートマトン A₁ で、0と1が交互に現れるすべての語（空語も含む）、つまり01、0101、010101、…の形の語を受理します。

もう1つのオートマトン A₂ は、0を少なくとも1つ含む語を受理します。

この2つの言語の和集合は、0を含むか、01、0101、…の形をした語の集合です。では、この和集合の言語を受理する有限オートマトン A = ⟨Q, Σ, δ, q, F⟩ をつくりましょう。まず、この新しいオートマトン A の状態がどうなるかを見てみます。1つ目と2つ目のオートマトンの状態の集合の直積です。

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

和集合の言語 L(A₁) ∪ L(A₂) を受理するオートマトン A の6つの状態は、このようになります。状態遷移図では次のようになります。

状態が状態の組でできていても、驚くことはありません。オートマトンの中で何が起きているのかをわかりやすくするためにすぎません。状態はふつうに q₀, …, q₅ という名前でもかまいません。受理状態は、状態 q₀ または p₁ を含む状態です。これらは、もとのオートマトンの受理状態です。初期状態は ⟨q₀, p₀⟩ です。

次に、すべての遷移を求めます。次のような表を書きます。

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

この表を順に埋めていきます。まず、状態 ⟨q₀, p₀⟩ から入力 0 でどこへ遷移するかを調べます。状態 q₀ から入力0でどこへ遷移するかをオートマトン A₁ で調べると、状態 q₁ です。オートマトン A₂ では、p₀ から0の遷移は状態 p₁ に向かいます。そこで、表に ⟨q₁, p₁⟩ と書きます。

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

入力1では、オートマトン A₁ について δ₁(q₀, 1) = q₂、オートマトン A₂ について δ₂(p₀, 1) = p₀ です。よって、状態 ⟨q₂, p₀⟩ が得られます。

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

表の残りを埋めます。

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

あとは、この表に従って状態遷移図の残りをかき加えるだけです。

オートマトンが正しく動くかを試してみましょう。語0100を受理するかを調べます。オートマトンは次の状態を順に通ります。

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

状態 ⟨q₂, p₁⟩ は受理状態なので、オートマトン A は語0100を受理します。では、語0100をオートマトン A₁ と A₂ に入力したら、どうなるでしょうか。オートマトン A₁ は次の状態を順に通ります。

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

オートマトンは受理状態でない状態 q₂ で終わるので、オートマトン A₁ はこの語を受理しません。オートマトン A₂ はどうでしょうか。

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

状態 p₁ は受理状態なので、オートマトン A₂ は語0100を受理します。オートマトン A₁ と A₂ が状態 q₂ と p₁ で終わったことは、オートマトン A が状態 ⟨q₂, p₁⟩ で終わったことと一致しています。

非決定性オートマトンを使う方法

例

正規言語の集合が和集合について閉じていることは、非決定性オートマトンをつくることでも証明できます。こちらのほうがずっと簡単です。

2つの正規言語 L₁, L₂ があり、その和集合 L = L₁ ∪ L₂ も正規言語であることを証明したいとします。L₁, L₂ は正規言語なので、これらの言語を受理するオートマトン A₁, A₂ が存在するはずです。つまり、L(A₁) = L₁ と L(A₂) = L₂ が成り立ちます。これらのオートマトンを使ってオートマトン A をつくり、言語 L を受理するように、つまり L(A) = L となるようにします。

有限オートマトン A₁ と A₂ が、それぞれ次のようになっているとします。

および

両方の言語の和集合を受理するオートマトンは、新しい初期状態をつくり、この状態からもとの2つの初期状態へ2本の ε 遷移を引けばつくれます。それだけです。オートマトンは次のようになります。

形式化

2つのオートマトン A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ と A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩ があります。オートマトン A = ⟨Q, Σ, δ, q₀, F⟩ をつくり、もとの2つのオートマトンが受理する言語の和集合を受理するように、つまり L(A) = L(A₁) ∪ L(A₂) となるようにします。このとき、次のように定めます。

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

遷移関数 δ は次のように定義します。

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & q \in Q_{1} & のとき \\ δ_{2} (q, a) & q \in Q_{2} & のとき \\ {q_{1}, q_{2}} & q = q_{0} \land a = ε & のとき \\ \emptyset & q = q_{0} \land a \neq ε & のとき \end{cases}$

参考文献

章: 正規言語の閉包性, 正規言語の和集合, 正規言語の共通部分, 正規言語の差集合, 正規言語の補集合, 正規言語の連接, 正規言語のクリーネ閉包

« 前へ: 正規言語の閉包性

次へ: 正規言語の共通部分 »