정규 언어의 교집합

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

증명의 아이디어

두 정규 언어 L₁과 L₂가 있고, 그 교집합 L₁ ∩ L₂가 다시 정규 언어임을 증명하려고 한다. L₁과 L₂는 정규 언어이므로 언어 L₁과 L₂를 인식하는 유한 오토마타 A₁과 A₂가 존재한다. 즉 L(A₁) = L₁이고 L(A₂) = L₂이다. 이제 언어 L₁ ∩ L₂를 인식하는 유한 오토마타 A를 만들면 언어 L₁ ∩ L₂가 정규 언어임이 증명된다.

문자열이 두 언어의 교집합에 속하려면 언어 L₁에도 속하고 L₂에도 속해야 한다. 즉 오토마타 A₁도 오토마타 A₂도 그 문자열을 수락해야 한다. 정규 언어의 합집합에서 쓴 아이디어를 그대로 쓰고, 수락 상태의 집합만 바꾸면 된다.

과정의 형식화

다음 두 오토마타가 있다.

$$\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}$$

언어 L(A₁) ∩ L(A₂)를 인식하는 오토마타 A = ⟨Q, Σ, δ, q, F⟩를 만든다. 이때 다음이 성립한다.

• 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