正規言語の補集合

正規言語 L を考えます。言語 L の補集合もまた正規言語であることを証明します。

補集合とは

言語 L の補集合とは、言語 L に属さないすべての語の集合です。補集合は $\bar{L}$ で表します。つまり、アルファベット Σ について次が成り立ちます。

$$\bar{L}=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}$$

例えば、記号1を少なくとも1つ含む語の言語なら、その補集合は、記号1を1つも含まない語の言語です。

手順

手順はとても簡単です。正規言語 L と、それを受理する決定性の完全なオートマトン A = ⟨Q, Σ, δ, q₀, F⟩ があるとします（どの有限オートマトンも、このようなオートマトンに変換できます）。オートマトン A' が言語 $\bar{L}$ を受理するようにするには、受理状態と非受理状態を入れかえて A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩ とします。手順はこれだけです。

例

次のオートマトンを考えます。

このオートマトンが受理する言語の補集合を受理するオートマトンは、次のようになります。

参考文献

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