[암호학] 11. Two-way Deterministic Push Down Automata

암호학을 위한 Computation Theory가 끝나가고 있다.

지금은 배경지식을 알아가는 단계이니 가벼운 마음으로 알아가보자.

 

Some Problems

여러가지 문제를 보자.

$L8 = \{x|x=y2y^R2y^R, y \in \{0, 1\}^*\}$

$L9 = \{x|x=y2y^R2y^R2y^R, y \in \{0, 1\}^*\}$

$L10 = \{x|x=yy^Ry^R, y \in \{0, 1\}^*\}$

$L11 = \{x|x=yy^Ry^Ry^R, y \in \{0, 1\}^*\}$

$L12 = \{x|x=yy, y \in \{0,1\}^*\}$

 

위 문제들은 DPDA로 해결할 수 없다.

특히 $L12$는 NPDA로도 해결할 수 없다. (ㄷㄷ..)

하지만 stack을 2개 사용하여 해결할 수 있다.

 

Two-way Deterministic Push Down Automata

DPDA에서 스택을 2개로 확장한 머신이다. (이하 T-DPDA)

 

T-DPDA를 이용해서 L8을 풀어보자.

0. 모드를 0으로 설정한다.

1. 0, 1을 입력받을 때마다 두개의 스택에 복사해서 넣는다.

2. 2를 받으면 모드를 1 더한다.

3-1. 모드가 1이면 0, 1을 입력받을 때마다 1번 스택에서 짝을 확인하고 pop한다.

3-2. 모드가 2이면 0, 1을 입력받을 때마다 2번 스택에서 짝을 확인하고 pop한다.

 

이런 느낌으로 스택이 하나일 때는 해결할 수 없는 문제도 해결할 수 있다.

그럼 스택 3개면 더 좋은 머신이겠네요?

이유는 모르지만 스택이 2개면 만능이라는 사실이 있다.

즉 스택이 3개나 2개나 해결할 수 있는 문제는 같다.

스택을 3개 사용하면 1개의 스택이 낭비된다는 뜻이다.

 

그리고 T-DPDA 와 Turing Machine의 성능이 같다!!

Turing Machine과 성능이 같다는 뜻은 C언어로 작성 가능하다는 뜻이다.

 

Queue Machine

Problem X7을 스택 머신으로 해결했으니 Problem X12는 큐 머신으로 해결할 수 있을 것 같다.

실제로 이는 해결할 수 있지만 큐 머신을 많이 연구하지 않는다고 한다.

스택 머신을 특히 많이 연구하는 이유가 컴파일러 때문이라고 한다.

애초에 괄호를 철저히 분석해야 syntax 에러를 잡아낼 수 있기 때문인가보다.