正規言語の差集合

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

証明の考え方

実は、証明することはほとんどありません。2つの集合の差集合については、次の関係が成り立つからです。

$$L_1\setminus L_2=L_1\cap \overline{L_2}$$

ここで、$\overline{L_2}$ は言語 L₂ の補集合です。正規言語の共通部分と正規言語の補集合の記事で見たように、正規言語はこの2つの演算について閉じています。つまり、言語の共通部分を受理するオートマトンも、言語の補集合を受理するオートマトンもつくれます。これらのオートマトンを使えば、言語 $L_1\cap \overline{L_2}$ を受理するオートマトンがつくれます。この言語は、言語 L₁ ∖ L₂ にほかなりません。

例

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

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

これらの言語の差集合を受理するオートマトンをつくります。そのためには、A₂ が受理する言語の補集合を受理するオートマトン A₂′ が必要です。受理状態と非受理状態を入れかえるだけです。

あとは、言語 L(A₁) と L(A₂′) の共通部分を受理するオートマトン A をつくるだけです。

参考文献

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