정규 언어의 연접

두 정규 언어 L₁, L₂가 있다고 하자. 이 두 언어의 연접 L = L₁ ∘ L₂도 정규 언어임을 증명해 보자.

연접이란

두 문자열 “010”과 “1111”을 연접하면 문자열 “0101111”이 된다. 언어의 연접은 한 언어의 각 문자열에 다른 언어의 각 문자열을 연접하여 만든 새 언어이다. 두 문자열과 두 언어의 연접은 동그라미 ∘로 나타낸다. 그러면 언어 L₁과 L₂의 연접은 다음과 같이 정의할 수 있다.

$L_{1} \circ L_{2} = {a \circ b | a \in L_{1}, b \in L_{2}}$

증명의 아이디어

두 정규 언어 L₁, L₂와 이 언어들을 인식하는 두 오토마타가 있다.

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{0}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, p_{0}, F_{2} ⟩ \end{array}$

두 오토마타 A₁과 A₂를 모두 “안에 품은” 비결정적 오토마타 A = ⟨Q, Σ, δ, q, F⟩를 만든다. 기본 아이디어는 이렇다. 먼저 오토마타 A₁로 문자열을 수락해 보고, 오토마타 A₁이 수락 상태에 이르면 문자열의 나머지 부분을 오토마타 A₂로 수락해 본다. 이 오토마타도 그 부분을 수락하면 오토마타 A는 문자열을 수락한다.

예

0으로만 이루어진 빈 문자열이 아닌 문자열과, 1 뒤에 0만 이어지는 문자열(1, 10, 100, …)을 수락하는 다음 오토마타 A₁이 있고

01로 끝나는 문자열을 수락하는 다음 오토마타 A₂가 있다고 하자.

오토마타 A₁의 모든 수락 상태에서 오토마타 A₂의 시작 상태로 가는 ε 전이를 추가한 다음, A₁의 수락 상태를 보통 상태로 바꾸어 두 오토마타를 연결한다. 새 오토마타 전체의 시작 상태는 오토마타 A₁의 시작 상태이다.

이 오토마타는 어떻게 동작할까? 먼저 오토마타 A₁의 동작을 시뮬레이션한다. 원래 수락 상태였던 q₁이나 q₂로 가면 오토마타 A₁이 문자열의 앞부분을 수락한다는 것을 알 수 있다. 문자열 전체가 언어 L₁ ∘ L₂에 속하려면 문자열의 나머지 부분을 두 번째 오토마타 A₂가 수락해야 한다. 그래서 원래 수락 상태였던 모든 상태에서 오토마타 A₂의 원래 시작 상태로 ε 전이가 나간다.

예를 들어 문자열 0001을 보자. 이 문자열은 문자열 00 ∘ 01의 연접으로 만들어질 수 있으므로 두 언어의 연접에 속한다. 하지만 문자열 0 ∘ 001의 연접으로도 만들어질 수 있다. 이 오토마타에서는 두 과정을 모두 시뮬레이션할 수 있다. 오토마타는 다음 경로를 따라갈 수 있다.

$q_{0} \to^{0} q_{1} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

이 경로에서는 오토마타가 먼저 문자열의 앞부분 00을 “수락”하고 그다음 뒷부분 01을 수락한다. 또는 다음 경로를 따라갈 수도 있다.

$q_{0} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

이 경우 오토마타는 먼저 앞부분 0을 “수락”하고 그다음 뒷부분 001을 수락한다. 물론 두 경우 모두 수락 상태 p₂에 도착한다.

형식적 구성

다시 정리하자. 두 정규 언어 L₁, L₂와 이 언어들을 인식하는 두 오토마타가 있다.

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{0}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, p_{0}, F_{2} ⟩ \end{array}$

다음을 만족하는 비결정적 오토마타 A = ⟨Q, Σ, δ, q, F⟩를 만든다.

Q = Q₁ ∪ Q₂ (단, Q₁ ∩ Q₂ = ∅이라고 가정한다)
Σ= Σ₁ ∪ Σ₂
q = q₀
F = F₂

전이 함수 δ는 경우를 나누어 정한다.

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & q \in Q_{1} \land q \notin F_{1} \\ δ_{1} (q, a) & q \in F_{1} \land a \neq ε \\ δ_{1} (q, a) \cup {p_{0}} & q \in F_{1} \land a = ε \\ δ_{2} (q, a) & q \in Q_{2} \end{cases}$

참고 자료

목차: 정규 언어의 닫힘 성질, 정규 언어의 합집합, 정규 언어의 교집합, 정규 언어의 차집합, 정규 언어의 여집합, 정규 언어의 연접, 정규 언어의 클레이니 폐포

« 이전: 정규 언어의 여집합

다음: 정규 언어의 클레이니 폐포 »