[암호학] 10. Push Down Automata

계속해서 배경지식에 대한 설명이 나오고 있다.

지금 내용들을 알아야 뒤에 나오는 개념들이 이해되니 천천히 알아보도록 하자..

 

Problem X5를 AC하는 머신이 있는가?

우리는 Problem X5가 DFA로 AC를 받을 수 없다는 것을 Pumping Lemma로 보였다

NFA로도 나타내기 힘들어 보이는데 여기에 stack를 하나 추가하는 것 만으로도 해결할 수 있다.

DFA에 stack을 추가한 머신을 Deterministic Push Down Automata라고 한다.

여담으로 머신 $\in$ 튜링머신(컴퓨터)이다.

 

Deterministic Push Down Automata (DPDA)

위에서 설명했듯이 DFA에 stack을 추가한 머신이다.

상태를 stack으로 관리하고 입력에 따라 스택에 넣을지 뺄지를 결정한다.

DPDA를 이용해서 Problem X5를 풀어보자.

 

1. 0을 받으면 stack에 넣고 1을 받으면 실패한다.

2. 0을 받다가 1이 나오면 stack에서 pop한다.

2-1. 0이 나오면 실패한다.

2-2. 1이 나왔는데 stack이 비어있으면 실패한다.

3. 입력이 끝나고 stack이 비어있으면 성공한다.

3-1. 입력이 끝났는데 stack이 안 비어있으면 실패한다.

 

이런 느낌으로 문제를 해결할 수 있다.

예제를 하나 더 보자

 

Problem X6

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

뭔가 난잡해보이는데 하나씩 살펴보자.

 

$y^R$은 $y$를 거꾸로 뒤집은 것이다.

예를 들어 $y = 0111$이면 $y^R = 1110$이다.

 

$2$는 그냥 $0, 1$과 다른 어떤 symbol이다.

 

$\{0, 1\}*$은 $0, 1$로 이루어진 길이 0 이상의 String이다.

 

DPDA를 이용해서 풀어보자.

1. 0, 1이 나오면 stack에 넣는다.

2. 2가 나오면 상태를 변환한다. (boolean변수를 쓰듯이 상태를 변환하면 된다.)

2-1. 2가 또 나오면 실패한다. (2는 한개만 가능)

3. 입력이 들어올 때마다 stack의 top 원소와 같은지 확인한다.

3-1. stack이 비었다면 실패한다.

3-2. 같으면 pop

3-3. 다르면 실패한다.

4. 입력이 끝났을 때 stack이 비었다면 AC, 아니라면 실패한다.

 

이렇게 DPDA를 사용하면 DFA로 표현할 수 없는 문제를 해결할 수 있다.

 

반면 다음 문제를 보자.

Problem X7

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

 

중간에 구분 symbol $2$가 없다는 이유로 X7은 DPDA가 AC할 수 없다.

만약에 그런 DPDA가 있다고 하면 $0110$을 AC할 것이다.

하지만 그렇게 되면 $01100110$을 AC하지 못한다.$\Box$ (반례판정법)

 

이것을 해결하기 위해 새로운 머신이 필요하다.

 

Non-Deterministic Push Down Automata (NPDA)

NPDA와 DPDA의 차이는 DFA와 NFA의 차이랑 같다.

NPDA는 stack에서 push할지 pop할지 정해져 있지 않기 때문에 모든 경우를 시뮬레이션 하고 한가지라도 AC를 받으면 문제를 해결한다는 뜻이다.

그럼 X7같은 문제도 NPDA는 모든 경우를 탐색하기때문에 $0110$까지만 확인해도 이것을 중간으로 보는 경우가 있기 때문이다.

계산량은 기하급수적으로 증가하지만 어쨋든 해결할수는 있다.

 

따라서 DPDA $\subset$ NPDA이다.