정규 언어의 합집합

두 정규 언어 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₂가 정규 언어임이 증명된다.

어떻게 만들까? 각 언어를 인식하는 유한 오토마타 A₁과 A₂가 있다. 문자열 w가 언어 L₁ ∪ L₂에 속하는 것은 오토마타 A₁, A₂ 중 적어도 하나가 이 문자열을 수락하는 것과 동치이다.

오토마타 A는 입력 w를 받으면 오토마타 A₁이 w를 입력받았을 때의 계산을 시뮬레이션하도록 동작할 수 있다. A₁이 문자열 w를 수락하면 A도 문자열 w를 수락한다. A₁이 문자열 w를 거부하면 A는 이어서 입력 w에 대한 A₂의 계산을 시뮬레이션해 본다. A₂가 문자열 w를 수락하면 A도 문자열 w를 수락한다. 그렇지 않으면 거부한다.

이제 오토마타 A가 다른 오토마타의 계산을 “시뮬레이션”한다는 것이 무슨 뜻인지 형식화하기만 하면 된다.

형식화

두 정규 언어 L₁과 L₂를 각각 다음 유한 오토마타가 인식한다고 하자.

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

언어 L = L₁ ∪ L₂를 인식하는 유한 오토마타 A = ⟨Q, Σ, δ, q, F⟩를 만든다. 두 오토마타 A₁, A₂를 시뮬레이션한다는 아이디어를 쓴다. 입력이 문자열 w = w₁w₂… w_n이고, 문자열 w에 대한 오토마타 A₁과 A₂의 진행을 동시에 시뮬레이션한다고 생각해 보자. 오토마타 A₁의 시작 형상은 ⟨q₁, w₁w₂… w_n⟩이고, A₂의 시작 형상은 ⟨q₂, w₁w₂… w_n⟩이다. 이제 각 오토마타에서 계산을 한 단계 진행하면 형상 ⟨δ₁(q₁, w₁), w₂… w_n⟩과 ⟨δ₂(q₂, w₁), w₂… w_n⟩에 이른다.

이 형상들은 첫 번째 성분만 다르고, 두 번째 성분인 아직 읽지 않은 부분은 언제나 같다. 그래서 시뮬레이션하는 동안 두 오토마타의 형상 두 개를 따로 유지할 필요 없이 ⟨⟨q_i, q_j⟩, w_l… w_n⟩ 꼴의 형상 하나로 충분하다. 여기서 q_i ∈ Q₁이고 q_j ∈ Q₂이다. 다시 말해 만들려는 오토마타 A의 시작 형상은 ⟨⟨q₁, q₂⟩, w⟩이다. 순서쌍 ⟨q₁, q₂⟩의 첫 번째 성분은 오토마타 A₁이 지금 있는 상태를 나타내고, 두 번째 성분은 오토마타 A₂의 현재 상태를 나타낸다.

따라서 만들려는 오토마타 A의 상태의 집합은 Q = Q₁ × Q₂, 즉 앞의 두 오토마타의 상태 집합의 곱집합이다. 그다음 아이디어는 이렇다. 오토마타 A의 시작 상태는 ⟨q₁, q₂⟩이고, 기호 w₁에 대해 오토마타 A₁이 상태 q_i로 가고 기호 w₁에 대해 오토마타 A₂가 상태 q_j로 가면 오토마타 A는 기호 w₁에 대해 상태 ⟨q_i, q_j⟩로 간다.

전이 함수 δ는 다음과 같이 쓴다(여기서는 지금 상태 q_i와 q_j에 있다고 가정한다).

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

이제 세부 사항만 남았다. 알파벳은 Σ= Σ₁ ∪ Σ₂이다. 시작 상태는 q = ⟨q₁, q₂⟩이다. 그리고 수락 상태는 q_i ∈ F₁이거나 q_j ∈ F₂인 모든 순서쌍 ⟨q_i, q_j⟩이다.

과정의 예

두 오토마타가 있다고 하자. 첫 번째 오토마타 A₁은 0과 1이 번갈아 나오는 모든 문자열(빈 문자열 포함), 즉 01, 0101, 010101, … 꼴의 문자열을 수락한다.

두 번째 오토마타 A₂는 0을 적어도 하나 포함하는 문자열을 수락한다.

두 언어의 합집합은 0을 포함하거나 01, 0101, … 꼴인 문자열이다. 이제 이 합집합 언어를 인식하는 유한 오토마타 A = ⟨Q, Σ, δ, q, F⟩를 만든다. 먼저 새 오토마타 A의 상태를 알아보자. 상태는 첫 번째 오토마타와 두 번째 오토마타의 상태 집합의 곱집합이다.

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

이것이 합집합 언어 L(A₁) ∪ L(A₂)를 인식하는 오토마타 A의 상태 6개이다. 상태 전이도에서는 다음과 같다.

상태가 상태의 순서쌍으로 이루어져 있다고 놀랄 필요는 없다. 오토마타 안에서 무슨 일이 일어나는지 알아보기 쉽게 하려는 것일 뿐이다. 상태 이름은 보통처럼 q₀, …, q₅여도 된다. 수락 상태는 원래 오토마타의 수락 상태인 q₀이나 p₁을 포함하는 상태이다. 시작 상태는 ⟨q₀, p₀⟩이다.

이제 전이를 모두 찾아야 한다. 다음과 같은 표를 만든다.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

그리고 표를 차례로 채운다. 먼저 입력 0에 대해 상태 ⟨q₀, p₀⟩에서 어디로 가는지 알아본다. 오토마타 A₁에서 입력 0에 대해 상태 q₀에서 나가는 전이는 상태 q₁로 간다. 오토마타 A₂에서 0에 대해 p₀에서 나가는 전이는 상태 p₁로 간다. 그래서 표에 ⟨q₁, p₁⟩을 적는다.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

입력 1에 대해서는 오토마타 A₁에서 δ₁(q₀, 1) = q₂이고 오토마타 A₂에서 δ₂(p₀, 1) = p₀이다. 따라서 상태 ⟨q₂, p₀⟩을 얻는다.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

표의 나머지를 채운다.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

이제 이 표에 따라 상태 전이도의 나머지를 그리면 된다.

오토마타가 제대로 동작하는지 확인해 보자. 문자열 0100을 수락해 보자. 오토마타는 다음 상태들을 차례로 거친다.

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

상태 ⟨q₂, p₁⟩이 수락 상태이므로 오토마타 A는 문자열 0100을 수락한다. 문자열 0100을 오토마타 A₁과 A₂로 수락해 보면 어떻게 될까? 오토마타 A₁은 다음 상태들을 차례로 거친다.

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

오토마타는 수락 상태가 아닌 상태 q₂에서 끝났으므로 오토마타 A₁은 이 문자열을 수락하지 않는다. 오토마타 A₂는 어떨까?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

상태 p₁은 수락 상태이므로 오토마타 A₂는 문자열 0100을 수락한다. 오토마타 A₁과 A₂가 상태 q₂와 p₁에서 끝났다는 점에 주목하자. 이는 오토마타 A가 상태 ⟨q₂, p₁⟩에서 끝난 것과 맞아떨어진다.

비결정적 오토마타를 이용한 방법

예

정규 언어의 집합이 합집합에 대해 닫혀 있다는 것은 비결정적 오토마타를 만들어서도 증명할 수 있는데, 이 방법이 훨씬 간단하다.

두 정규 언어 L₁, L₂가 있고, 그 합집합 L = L₁ ∪ L₂도 정규 언어임을 증명하려고 한다. L₁, L₂는 정규 언어이므로 이 언어들을 인식하는 오토마타 A₁, A₂가 존재해야 한다. 즉 L(A₁) = L₁이고 L(A₂) = L₂이다. 이 오토마타들로 언어 L을 인식하는, 즉 L(A) = L인 오토마타 A를 만든다.

유한 오토마타 A₁과 A₂가 다음과 같다고 하자.

그리고

두 언어의 합집합을 인식하는 오토마타는 새 시작 상태를 만들고, 이 상태에서 원래 시작 상태들로 가는 ε 전이 두 개를 두면 만들어진다. 이것으로 끝이다. 오토마타는 다음과 같다.

형식화

두 오토마타 A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩과 A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩가 있다. 앞의 두 오토마타가 인식하는 언어의 합집합, 즉 L(A) = L(A₁) ∪ L(A₂)를 인식하는 오토마타 A = ⟨Q, Σ, δ, q₀, F⟩를 만든다. 이때 다음이 성립한다.

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

그리고 전이 함수 δ는 다음과 같이 정의한다.

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

참고 자료

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

« 이전: 정규 언어의 닫힘 성질

다음: 정규 언어의 교집합 »