정규 언어의 차집합

두 정규 언어 L₁, L₂가 있다고 하자. 이 두 언어의 차집합 L = L₁ ∖ L₂도 정규 언어임을 증명해 보자.

아이디어

사실 증명할 것이 별로 없다. 두 집합의 차집합에 대해 다음 관계가 성립하기 때문이다.

$$L_1\setminus L_2=L_1\cap L_2^C,$$

여기서 $L_2^C$은 언어 L₂의 여집합이다. 정규 언어의 교집합과 정규 언어의 여집합을 다룬 글에서 정규 언어가 두 연산에 대해 모두 닫혀 있음을 보였다. 즉 언어의 교집합을 인식하는 오토마타와 언어의 여집합을 인식하는 오토마타를 만들 수 있다. 따라서 이 오토마타들로 언어 $L_1\cap L_2^C$을 인식하는 오토마타를 만들 수 있고, 이 언어가 곧 언어 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