[형식언어] 유한 오토마타의 닫힘 성질

유한 오토마타의 닫힘 성질

먼저 유한 오토마타의 닫힘 성질에 대한 정리를 살펴보자. 만약 L₁, L₂가 정규 언어라면, L₁ ∪ L₂, L₁ ·L₂, L₁*은 정규 언어이다. 즉, 정규 언어는 합집합, 접속, 클로저에 대해 닫혀있다. 정규 언어의 합집합은 간단하게 두 문법의 Product rule을 합쳐주어 두 정규 언어를 합집합 연산 할 수 있다. 

 

 P₁: S₁ -> 0S₁    S₁ -> 0, P₂: S₂ -> 1S₂    S₂ -> 1의 두 문법이 생성하는 언어의 합집합을 구해보자. 위 정리에서 정규 언어의 합집합은 두 문법의 생성 규칙을 합쳐주면 된다고 하였으니, 합집합에 대한 생성 규칙 P는 P₁ ∪ P₂ ∪ {S -> S₁ | S₂}로 다음과 같다.

P: S -> S₁    S -> S₂    S₁ -> 0S₁    S₁ -> 0    S₂ -> 1S₂    S₂ -> 1

 

이것을 다음과 같이 바꿀 수 있다.

S -> 0S₁ | 0 | 1S₂ | 1,     S₁ -> 0S₁ | 0,    S₂ -> 1S₂ | 1.

 

접속 연산은 한 오토마타의 종결 상태를 다른 오토마타의 시작 상태로 간주하면 된다. 이것은 아래 예시를 보며 살펴보자.

 M₁ 오토마타의 종결 상태 B에 대해 M₁ 오토마타의 종결 상태 B에서 심볼을 본 상태와 접속할 오토마타 M2의 시작 심볼 X에서 심볼을 본 상태를 합집합한다. 즉, B와 X에서 입력 심볼 0을 보고 갈 수 있는 상태와 입력 심볼 1을 보고 갈 수 있는 상태를 추가하면 된다. 상태 B에서 입력 심볼 0을 보고 도달할 수 있는 상태는 없고, M₂의 상태 X에서 심볼 0을 보고 종결 상태 Y로 이동할 수 있다. 따라서 상태 B에서 입력 심볼 0을 보고 상태 Y로 이동할 수 있도록 지시선을 추가해 준다. 상태 B에서 입력 심볼 1을 보고서는 상태 B로, 상태 Y에서 입력 심볼 1을 보고 종결 상태 Y로 이동할 수 있다. 따라서 이 경우도 추가해주면 가장 아래처럼 M₁ · M₂ 오토마타가 된다.