정규 언어의 클레이니 폐포

정규 언어 L이 있다. 언어 L의 클레이니 폐포가 다시 정규 언어임을 증명해 보자.

언어의 클레이니 폐포란

언어 L의 클레이니 폐포는 L^∗로 나타낸다. 클레이니 폐포에는 언어 L의 문자열을 유한개 연접하여 만들 수 있는 모든 문자열이 들어 있다. 클레이니 폐포는 다음과 같이 정의할 수 있다.

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in {\mathbb{N}}_0\},$$

여기서 ∘는 연접 연산이다. 클레이니 폐포에는 빈 문자열 ϵ도 들어 있다.

형식적 구성

언어의 연접과 매우 비슷하게 진행한다. 다만 서로 다른 두 오토마타를 연결하는 대신 오토마타 하나를 자기 자신과 연결한다. 즉 오토마타의 수락 상태에서 그 오토마타의 시작 상태로 ε 전이를 둔다. 그런데 클레이니 폐포에는 빈 문자열도 들어 있어야 한다. 어떻게 하면 될까? 시작 상태를 수락 상태로 바꿀 수도 있다. 그러면 이 오토마타는 빈 문자열을 수락하지만, 원래 수락하면 안 되는 다른 문자열까지 수락할 수 있다. 그래서 그 대신 새 시작 상태를 만들고, 이 새 시작 상태에서 원래 시작 상태로 가는 ε 전이를 둔다.

정규 언어 L₁과 이 언어를 인식하는 다음 오토마타가 있다.

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

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

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

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

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& & q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& & q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& & q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& & q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& & q=q_s\wedge a\ne ϵ\end{array}$$

예

문자열 00 또는 11을 수락하는 다음 오토마타 A₁이 있다고 하자.

언어 L(A₁)의 클레이니 폐포는 00과 11을 이어 붙여 만든 모든 문자열의 언어, 예를 들어 0000, 110011, 11110000 등으로 이루어진 언어이다. 이 클레이니 폐포를 인식하는 오토마타는 원래 시작 상태 q₀으로 가는 ε 전이가 있는 새 시작 상태 q_s를 만들고, 상태 q₃과 q₄에서 상태 q₀으로 가는 ε 전이를 추가하여 만든다.

이 오토마타가 실제로 문자열 0000, 110011, 11110000을 수락하고, 예를 들어 문자열 1010은 수락하지 않는다는 것을 확인할 수 있다.

참고 자료

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