正規言語の共通部分

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₂ が正規言語であることを証明できます。

語が言語の共通部分に属するのは、その語が言語 L₁ と L₂ の両方に属するときです。つまり、オートマトン A₁ とオートマトン A₂ の両方がその語を受理しなければなりません。正規言語の和集合で使ったのとまったく同じ考え方を使い、受理状態の集合だけを変えます。

手順の形式化

次の2つのオートマトンがあります。

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

オートマトン A = ⟨Q, Σ, δ, q, F⟩ をつくり、言語 L(A₁) ∩ L(A₂) を受理するようにします。このオートマトンは次のように定めます。

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

遷移関数 δ については、次の関係が成り立ちます。

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

例

1を偶数個含むすべての語を受理する、次のオートマトン A₁ を考えます。

また、0を奇数個含む語を受理する、次のオートマトン A₂ も考えます。

これらの言語の共通部分を受理するオートマトンをつくります。このオートマトンの状態の集合は Q = Q₁ × Q₂ の形で、初期状態は状態 ⟨q₀, p₀⟩、受理状態は F₁ × F₂ です。

次に、δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩ となるように遷移をつけ加えます。

例えば、このオートマトンには、状態 ⟨q₀, p₀⟩ から記号0で状態 ⟨q₀,p₁⟩ に向かう遷移があります。これは、オートマトン A₁ には状態 q₀ から記号0で再び状態 q₀ にもどる遷移があり、オートマトン A₂ には記号0で状態 p₀ から状態 p₁ に向かう遷移があることに対応しています。

オートマトンを試してみましょう。110や00000のような語は受理し（1を偶数個含み、しかも0を奇数個含みます）、11、111、1010のような語は受理しないはずです。

参考文献

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools