[Automata] Push Down Automata(PDA)

Push Down Automata(PDA)

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

# Push Down Automata

이전 포스트에서 RE(Regular Expression)으로 표현이 되지 않는 경우 CFG(Context Free Grammar)로 표현한다는 것을 알아보았다.

CFG로 RE 표현이 안 되는 Language를 표현하지만 이를 DFA나 NFA에 적용할 수는 없다.

따라서 CFG를 Automaton으로 나타내기 위해서는 Pushdown automata를 사용하여 나타낼 수 있다.

Pushdown automata의 큰 특징은 stack을 사용한다는 것이며, 이에 따라 데이터를 쌓는 것뿐만 아니라 내보내 주는, 즉 Pop 하는 특징도 가지고 있다.

한마디로 쉽게 얘기하면 NFA나 DFA에서는 반복과 다음 state로 이동까지만 존재했다면, Push down automata에서는 필요에 따라 같은 state에 남아 있거나, stack에 있는 하나의 element를 버리고 다음 state로 가는 방식을 가지고 있다.

---

# Formal Definition

PDA의 Formal definition은 아래와 같다.

A PDA has (K, Σ, Γ, s, F, Δ).

• K is a set.
• Σ is an alphabet.
• Γ is a set, which is a finite stack alphabet.
• s is a start state, which is an element of K.
• F is a final state, which is a subset of K.
• Δ is a transition relation, a subset of ((K x (Σ U {e}) x Γ^*) x (K x Γ^*))

---

# Push and Pop

PDA에서 Push와 Pop은 '/'로 구분하여 나타낸다.

예를 들어서 a를 push 하고 b를 pop 하고 싶다면, a/b라고 표현한다.

e/a는 pop하는게 e이기 때문에 없다는 것이며, a를 push 한다는 의미이다.

반대로 a/e는 a를 pop 해서 내보낼 겄지만 push 되는 건 없다는 걸 의미한다.

---

# Push Down Automaton Examples: L = {0^n1^n | n >= 1}

Fig01. PDA Examples

위의 Automaton은 PDA 방식을 따르고 있는 Automaton 디자인이다.

PDA의 특징인 RE가 될 수 없는 Language를 표현해주는 오토마톤이자, Stack을 사용하여 Push와 Pop이 존재한다.

위의 예제 PDA가 나타내는 Language 조건은 아래와 같다.

L = {0^n1^n | n >= 1}

위의 예제 PDA가 L = {0^n1^n | n >= 1}을 어떻게 나타내고 있는지를 설명하기 위해서는 먼저 제시된 Language 조건을 살펴봐야 한다.

L = {0^n1^n | n >= 1}의 경우에는 0과 1이 n의 제곱으로 반복이 이루어지면 n은 1보다 크거나 같다는 의미를 가지고 있다.

따라서 만약에 n=2 일 경우에는 0011이 산출되고 n=5일 경우에는 0000011111이 된다.

결과적으로 위의 조건은 0과 1일 똑같은 n번으로 늘어나지만 01010과 같이 섞여있는 것이 아니라 0이 먼저 나오고 1이 다음으로 나온다.

이러한 경우에는 PDA에서 0을 반복해서 stack 할 수 있게 하면서도 1이 stack 되고 나서는 0이 더 이상 stack 되지 않고 pop 돼서 나와야 한다.

따라서 첫번째 q1 state에서는 e/0으로 0이 쌓이지만 q2부터는 1이 입력되기 때문에 0이 pop 돼서 나오는 걸 알 수 있다.

마지막으로 최종 q2에 도달하면 모든 stack에 elements들이 없어야 한다.

한마디로 원하는 결과를 위해서 필요 없이 많은 0의 경우에는 잠시 stack을 해두었다가 pop 하여 없애주는 방식을 가지고 있는 셈이다.

---

# PDA Examples: L = {wcw^R ∣ w ∈ {a, b}^*}

Fig02. PDA Examples

 

---