[Compiler]TCA(Thompson's Construction Algorithm)

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다.

 

출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler

 

이전에 경로를 찾는데 모든 가능성을 주목한 방식이 NFA이고 진짜 정답을 찾는 것이 DFA였다. 

우리는 Lexical Analysis를 통해 정규 표현식을 NFA로 거쳐 DFA를 거치는 것이다.

 

그렇다면 정규 표현식을 NFA 형식으로 바꾸는 방식이 있을텐데 이것이 TCA(Thompson's Construction Algorithm)이다. 정규 표현식을 가장 기본적인 단위로 쪼개어 NFA에서 정의한 방식대로 합치는 것이다.

 

여기서 가장 본적인 단위는  ϵ 와 'a 의 시그마' 이다. 처음 상태에서 포함된 요소를 선택하면 다음 상태로 넘어간다 라고 이해하자. 

 

NFA N(s)와 N(t) 가 있을 때, s, t가 결헙된 형태를 어떻게 찾느냐 이다. 

 

 

위 그림처럼 Union 된 형태일 수 있다. 찾고자 하는 문자 a가 s|t 의 형태라면 현재 상태에서 다음 상태로 넘어갈 때, N(s)나 N(t)로만 가면 된다. 임의로 ϵ 을 이용하여 연결한다.

Concatenate의 경우 교집합의 모양으로 N(s), N(t)를 묶어 연결하여 표현해주면 된다.

 

실제 예제를 좀 더 사용해보자, 두 NFA가 아래와 같고 (A|B)*ABB의 NFA 형식을 구해보자

 

 

여기서 발견할 수 있는 기본적인 요소는 Union도 있고 Kleene Closure도 있고, ABB라는 Concatenate 형태도 있다. 이 기본 요소들을 TCA로 표현할 수 있다. 먼저 A|B의 형태이고 어떤 state를 통과해서든지 final state로 전이되는 형태이기 때문에 다음과 같이 표현할 수 있다.

 

A|B, (A|B) : 처음 상태가 1이고 final state가 6인 상태 - Union

 

다음은 Kleene Closure의 형태인데 이 형태는 A|B를 구성하는 요소 중 하나이므로 처음상태와 마지막 상태를 삽입해서 표현한다.

 

(A|B)* : Kleen Clousre는 ϵ 을 이용하여 쉽게 만들 수 있다.

 

이제 ABB의 Concatenate를 구하자

(A|B)*ABB : ABB 자체가 이미 Path가 있다.

이것이 TCA를 통한 (A|B)*ABB의 NFA형식이다. 즉 a = (A|B)*ABB 라는 정규 표현식인데 N(a)를 구할 수 있는 쉬운 방법이 TCA이다. 

 

TCA를 통해 구한 NFA는 다음의 특징이 있다.

 

- 한개의 state에서는 최대 2개의 branch transition을 가진다.

 

- NFA는 반드시 한개의 start state와 한개의 accepting state(final state)로 구성

 

- 보통 원래 state의 최대 2배까지 많은 state를 가지게 된다.