[오토마타] 18. NPDA

지금까지 CFG와 CFG를 통해 만드는 언어 CFL, 그리고 어떤 문장이 CFL에 속하는지 판단하는 파싱, 파싱을 편하게 하기 위한 문법 변환 방법들과 DP 알고리즘으로 파싱하는 CYK 알고리즘을 알아보았다.

 

이번 글에서는 마치 RL을 DFA와 NFA로 나타낼 수 있었던 것처럼, CFL을 표현하는 기계를 정리해본다.

CFL은 PushDown Acceptor(PDA) 로 표현할 수 있다.

 

 

위에 적은 말을 그림으로 표현하면 위와 같다.

CFL에서는 regular expression 에 해당하는 요소는 존재하지 않는다.

 

 

CFL을 표현하는 NPDA는 제한없이 개수를 카운팅할 수 있거나, 시퀀스의 순서를 저장할 수 있어야 한다.

(기존의 DFA, NFA는 유한 상태 기계로, 카운팅할 수 있는 제한이 존재했다.)

 

 

위에 예시로 등장한 언어는 모두 CFG로 표현할 수 있는, CFL이기 때문이다.

그래서 PDA는 무한한 저장공간을 가진다.

 

 

PDA는 저장공간으로 그림에 보이는 것처럼 스택을 활용한다.

 

NPDA

이번 글에서는 Nondeterministic PushDown Acceptor(NPDA)를 먼저 정의한다.

 

NPDA는 위와 같이 정의한다.

기존의 RL을 나타낼 때 사용했던 NFA는 M=(Q, Σ, 𝛿, q0, F) 로 이루어져있었다.

NPDA 에서도 같은 기호는 같은 의미를 갖는다.

 

그래서 새롭게 추가된 기호 위주로 내용을 정리해보면,

Γ 은 대문자 '감마'로, 스택 알파벳을 말한다. (스택 알파벳은 input 알파벳인 Σ와 달라도 괜찮다.)

z 는 스택의 start symbol 을 말한다. 스택에 처음부터 들어있는 문자로, 이 문자를 통해서 현재 스택이 비어있는지 판단할 수 있다.

𝛿 는 똑같이 transition function을 의미하는데, NFA 와는 그 정의가 다르다.

 

 

 

NFA에서는 Q x (Σ + λ) 였지만, NPDA 에는 추가로 스택 알파벳 조합까지 추가한 서브셋을 말한다.

여기에서 Q는 현재 상태, Σ는 현재 읽은 문자 (λ-transition 도 가능), Γ는 현재 스택에 들어있는 문자를 말한다.

그리고 그 상태에서 전이하는 것은 Q x Γ* 의 서브셋으로, 화살표 오른쪽의 Q는 다음 상태, Γ* 는 스택에 새로 추가할 심볼(들)을 말한다.

트랜지션이 발생할 때는, 반드시 스택에서 하나의 원소를 빼게 되는데, 이 원소가 빠지지 않기를 원하는 경우에는, 빠지는 원소를 다시 넣으면 된다.

 

 

간단한 NPDA 예시를 보면 위와 같은 트랜지션 함수의 의미는 다음과 같다.

 

만약 현재 상태가 q1 이고, 현재 읽은 심볼은 a이며, 스택에서 pop 한 값이 b일 때,

 

1. q2 상태로 이동하면서 스택에 cd 를 넣거나 (이때 심볼은 오른쪽부터 넣는다. 따라서 d를 넣고, c를 넣으면 스택의 top에는 c가 있다.)

2. q3 상태로 이동하면서 스택에 아무것도 넣지 않을 수 있다. (λ)

 

 

 

이번엔 조금 더 복잡한 NPDA 를 살펴보자.

상태는 4개가 존재하고, 읽어들이는 심볼은 a, b, 스택에는 0, 1 이 저장될 수 있다.

초기에 스택에 들어있는 값은 0이고, final state 는 q3 1개이다. (여러개 있을 수도 있다.)

 

트랜지션 함수를 보면 q0 에서 시작해서 a를 읽었을 때, 스택에서 pop 한 값이 0이면 q1 또는 q3 로 갈 수 있는데,

q1으로 가게되면 스택에 10을 넣는다. 이때 오른쪽에서부터 넣으므로 0과 1이 들어가게 되고,

이는 결국 처음에 뺐던 0을 그대로 복구해 넣으면서 동시에 1을 새로 추가하는 형태로 해석할 수 있다.

반면 q3로 갈 때는 스택에 아무것도 안 넣으므로 스택의 데이터가 1개 빠지는 효과가 발생한다.

 

이 그림에 initial state 로 들어오는 간선도 그려야 한다.

 

트랜지션 그래프를 그려보면 이렇게 그릴 수 있다.

간선에는 읽은 input symbol, 스택에서 pop 한 심볼, 스택에 넣을 심볼 순으로 기재한다.

(NFA에서는 input symbol 만 표기하면 되었지만, NPDA 에서는 스택이 추가되므로 스택 관련 정보도 기술한다)

 

 

 

강의록에서는 이렇게 그렸다.

나는 간선을 여러개 그렸는데, 간선 하나에 라벨을 여러 나열해서 쓸 수도 있다.

 

이제 이 트랜지션 그래프에 따른 NPDA 동작을 따라가보자.

먼저 예시로, 문장인 λ 를 넣어보자.

 

1. 초기상태에는 스택에 0이 들어있고, q0 상태에서 시작한다.

2. 람다를 읽었을 때 스택에서 0을 pop했다. q0 에서 (λ, 0, λ) 에 대한 간선이 있다.

따라가보면 q3로 이동하고 λ를 push 한다.

3. 모든 문자를 다 읽었으며 final state 에 도착했으므로 문장이다.

 

따라서 λ 가 문장임을 잘 판별했다.

다른 예시로 a를 넣어보자. (위 예제 문제를 보면, a도 문장임을 알 수 있다. L에 합집합으로 {a}를 했기 때문)

 

1. 초기상태에는 스택에 0, 상태는 q0

2. a를 읽었고, 스택에서 0을 pop 한다. 갈 수 있는 상태가 2개 있는데, 일단 바로 q3로 이동하고 λ 를 푸시한다.

3. 모든 문자를 다 읽었고 final state 이므로 문장이다.

 

다른 예시로 aabb를 넣어보자.

 

1. 초기 상태는 동일하고

2. a가 들어오고 스택에서 0을 팝한 상황, 사용 가능한 트랜지션 함수가 2개 있으나, q1로 가는 선택지를 고른다.

스택에 10 을 넣으므로, 0과 1을 차례대로 넣어서 스택의 top에는 1이 존재한다.

3. 다시 a가 들어오고 스택에서 1을 팝한 상황, 이때는 트랜지션 함수가 유일하며, q1로 유지하고 11을 넣는다.

(기존에 뺐던 1을 다시 추가하고 새로운 1도 넣는 것)

4. b가 들어오고 스택에서 1을 팝한 상황, 이때도 트랜지션 함수가 유일하며 q2로 상태를 이동하고 스택에는 아무것도 넣지 않는다.

5. b가 들어오고 스택에서 1을 팝한 상황, 이때도 트랜지션 함수가 유일하며 q2로 상태를 유지하고, 스택에는 아무것도 넣지 않는다.

6.남은 input 심볼이 없어서 λ이고 스택에서 0을 팝한 상황, 이때도 트랜지션 함수가 유일하며, q3으로 상태를 이동하고 스택에는 아무것도 넣지 않는다.

 

최종 목적지가 q3이므로 문장이다.

 

그래서 이 기계가 문장을 판별하는 원리를 보면,

a를 읽으면 스택에 1을 쌓아두고, b를 읽으면 스택에서 1을 뺀다.

모든 심볼을 다 읽었을 때 스택에 0이 남아있다면 문장인 것이다.

사실상 스택에 들어있는 1의 개수는 a와 b의 개수의 차이를 나타낸다고 볼 수 있다. (a가 얼마나 더 많은지)

 

---

Move

이제 어떤 심볼이 들어왔을 때, NPDA에서 어떻게 동작을 했는지 기술하는 방법을 알아보자.

DFA, NFA 에서는 (상태, 심볼) → 상태 꼴로 어떻게 트랜지션이 발생하는지 기술할 수 있었다.

NPDA에서는 트랜지션 함수의 형태 뿐만 아니라

(상태, 아직 읽지 않은 문자열, 현재 스택 내용)├ (상태, 아직 읽지 않은 문자열, 현재 스택 내용) 꼴로도 기술할 수 있다.

├ 기호 좌우에 있는 3-tuple을 가리켜 instantaneous description 이라고 부르며,

현재 상태 뿐만 아니라, 미래의 상태를 같이 나타내며 instantaneous description 이 어떻게 변화하는지를 나타낸다.

그리고├ 기호를 써서 현재의 상태와 미래의 상태를 함께 표현하는 것을 move 라고 한다.

트랜지션 함수에서와 마찬가지로 move 에도 * 기호를 써서 ├* 와 같이 표기할 수 있고, 이 표기는 임의 횟수의 move를 적용한 것을 나타낸다.

 

 

이렇게 보는 게 더 이해가 잘된다.

현재 aw 라는 읽지 않은 파트가 남았기에 a를 읽고나면 그 다음의 읽지 않은 파트는 w가 된다.

스택에는 bx 라는 데이터가 있었다면 팝을 하고나서 y를 넣을 때 다음의 스택 내용은 yx가 된다.

 

 

이를 그림으로 보면 위와 같다.

 

이제 NPDA가 받아들이는 언어 L(M)은 다음과 같이 move를 사용하여 기술할 수 있다.

 

 

L(M)에 속하는 문장 w를 Σ 에 속하는 알파벳으로 만든 문자열이며, 다음을 만족한다.

(q0, w, z) 라는 i.d 에서 출발해서 임의의 move를 가쳤을 때, (p, λ, u) 가 된다.

이때 p는 final state 집합에 속해있고, u는 Γ 에 속한 임의 심볼이다. (즉, 스택이 비어있어도 되고 뭔가 들어있어도 된다.)

그리고 아직 읽지 않은 문자열은 없어야 하므로 가운데에 λ가 들어있다.

 

결론만 말하면, 스택의 상태는 중요하지 않고, 초기 상태에서 임의의 move를 계속 했을 때, 모든 문자열을 다 읽은 순간 그 상태가 final state인 경우가 존재하면 해당 문자열은 L(M) 에 속한다는 것이다.

 

 

연습문제를 풀어보자.

L은 a와 b의 개수가 같은 문자열을 문장으로 받아들이는 언어이다. (순서는 중요하지 않다.)

기계를 만들고 예시로 baab도 넣어서 돌려보자.

 

먼저 기계를 만드는 아이디어는 다음과 같다.

스택에는 a와 b의 개수 차이를 관리하려고 하는데, 순서가 중요하지 않기 때문에 어떤 시점에는 b가 더 많을 수도 있고, 어떤 시점에는 a가 더 많을 수도 있다.

 

그래서 a가 더 많은 경우에는 그 개수 차이만큼 0을 넣고, b가 더 많은 경우에는 그 개수 차이만큼 1을 넣는다고 하자.

그리고 개수가 같은 상태를 관리하기 위해서 z라는 변수를 사용한다고 해보자.

즉, Γ = { 0, 1, z } 이다.

 

이제 NPDA가 동작할 때는

현재 a를 읽었을 때 개수가 같았다면 (z를 pop했다면) 이제 a가 많아지므로 0을 추가하고 (0z 추가)

현재 a를 읽었을 때 개수가 더 많았다면 (0을 pop했다면) a가 더 많아지므로 0을 추가하고 (00 추가)

현재 a를 읽었을 때 개수가 더 적었다면 (1을 pop했다면) b와의 개수 차이가 줄어드므로 1을 제거한다. (λ추가)

 

현재 b를 읽었을 때도 비슷하게 동작하면 된다.

 

판단을 마무리하고 final state로 갈 때는 모든 스트링을 다 읽어서 λ를 읽었을 때, 스택에서 꺼낸 것이 z라면 문장으로 판단하면 된다.

 

따라서 필요한 상태는 2가지이다.

a = b 인 상태, a ≠ b 인 상태

 

따라서 NPDA는 M = (Q, Σ, Γ, 𝛿, z, q0) 에서

𝛿만 정의하면 되는데, 𝛿는 위에 상술한 NPDA가 동작하는 방법을 그대로 묘사하면 된다.

 

하나만 해보면,

a를 읽었을 때 개수가 같았다면 a가 많아지므로 0을 추가하는 경우,

𝛿: (q0, a, z) → {(q0, 0z)} 와 같이 쓸 수 있다. (NPDA이므로 집합 형태로 결과를 써주어야 하는 것에 주의하자.)

 

트랜지션 그래프를 그려보면

 

 

이렇게 그릴 수 있다.

(교수님은 q0 → q1 에 대해 (λ, z, z) 와 같이 쓰셨는데, 어차피 q1에서 더 읽을 것이 없어서 상관없을 듯 하다.)

(라벨을 적을 때 여러 개를 적는 경우, ; 을 사용해서 구분해주셨다.)

 

이제 baab 에 대해 수행하는 것을 instantaneous 간의 move로 표현해보면

 

 

이렇게 표현할 수 있다.

그리고 NPDA는 baab 라는 문자열을 문장으로서 받아들인다. (accept)

 

 

 

(추가 예정)