정규 언어의 여집합

정규 언어 L이 있다. 언어 L의 여집합이 다시 정규 언어임을 증명해 보자.

여집합이란

언어 L의 여집합은 언어 L에 속하지 않는 모든 문자열의 집합이다. 여집합은 L^C으로 나타낸다. 즉 알파벳 Σ에 대하여 다음이 성립한다.

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

예를 들어 기호 1을 적어도 하나 포함하는 문자열의 언어의 여집합은 기호 1을 하나도 포함하지 않는 문자열의 언어이다.

방법

방법은 아주 간단하다. 정규 언어 L과 이 언어를 인식하는 결정적 완전 오토마타 A = ⟨Q, Σ, δ, q₀, F⟩가 있다(모든 유한 오토마타는 이런 오토마타로 바꿀 수 있다). L^C을 인식하는 오토마타 A'은 수락 상태와 비수락 상태를 서로 바꾸어 만든다. 즉 A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩이다. 이것으로 끝이다.

예

다음 오토마타가 있다고 하자.

이 언어의 여집합을 인식하는 오토마타는 다음과 같다.

참고 자료

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