[오토마타] 24. RL vs CFL vs TM

이번 글에서는 지금까지 배운 내용을 토대로 RL, CFL, TM 을 비교해본다.

 

 

aⁿ 은 레귤러 언어로서, DFA로 그릴 수 있었고, RE로 표현할 수도 있었고, 위와 같은 RG로 표현할 수도 있었다.

(RG는 Linear Grammar 중에서 변수가 왼쪽에만 있거나, 오른쪽에만 있는 형태이면 된다.)

 

 

 

CFL 의 경우, 대표적인 예시가 aⁿbⁿ 으로, 펌핑 렘마를 통해 RL 가 아님을 보일 수 있었고,

CFG 를 통해 표현하거나, NPDA를 통해 표현할 수 있었다.

 

 

 

마지막으로 CFG 가 아닌 언어로 대표적인 것이 aⁿbⁿcⁿ 이었다. (이때, n ≥ 1 이어야 한다. 튜링머신은 λ를 취급하지 않기 때문)

이 언어는 펌핑 렘마를 통해 CFL이 아니라는 것을 보일 수 있었고, 지난 글에서 마지막 예제 문제를 풀어본 것처럼, 튜링 머신으로 만들 수도 있었다.

 

그렇다면 이런 언어를 문법으로도 기술할 수 있을까?

바로 위 그림에서 보는 것처럼 기술이 가능하다.

현재 화살표 왼쪽에 변수 하나 말고도 터미널이 같이 등장하는 것을 볼 수 있다.

따라서 이 문법은 CFG가 아니다.

 

이 문법에서 대문자 A 는 일종의 메신저 또는 TM 에서 헤드라고 생각하면 된다.

A가 하는 일은 오른쪽에 b가 있는지 확인하고, c까지 있다면 abc를 만드는 일을 도와주는 역할을 수행한다.

 

Ab 를 읽었다면 A 오른쪽에 b 가 존재한다는 뜻이므로, bA 로 produce 하여 마치 헤드를 오른쪽으로 한칸 이동시키는 것과 같이 만든다.

Ac 를 읽었다면 c까지 모두 만난 것이니 abc를 만들면 된다. 이때 bc만 만든 이유는 a, b, c를 각각 한군데에 몰아넣어야 하기 때문에 A를 만들 위치는 B 라는 새로운 포인터를 통해 찾아서 넣어준다. 따라서 Bbcc 를 생성한다.

 

B는 계속해서 왼쪽으로 이동하여 a를 추가할 위치를 찾아야 한다.

따라서 bB 로 왼쪽에 b가 존재하면 Bb 로 왼쪽으로 이동하고

aB 로 해서 a를 만나면, 이 위치에 aa 로서 a 를 추가하고 모든 과정을 종료하거나, aaA 를 produce해서 다음에 abc를 추가할 수 있도록 A 포인터를 세팅한다.