Outline
| Language |
RL |
CFL |
| Expression |
RE |
CFG |
| Deterministic Automata |
DFA |
Deterministic PDA |
| Non-DA |
NFA |
Non-D PDA |
RL=RE=DFA=NFA
CFL=CFG=NPDA ≠ DPDA
Pushdown Automata (PDA)
NFA with Stack
Nondeterministic Pushdown Automada (NPDA)
$M = (Q,\Sigma, \Gamma, \delta, q_0, Z_0, F)$
- $Q$: finite set of states
- $\Sigma$: finite set of input symbols ( stack alphabet )
- $\Gamma$: finite set of Stack symbols ( stack alphabet )
- $\delta$: $Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to$ all finite subsets of $Q \times \Gamma ^*$
- q0: start state
- Z0: start stack symbol
- F: set of final accepting state
Transition Function
$\delta ( q, a ,X ) \to$ set of $(p, \gamma)$
q라는 state에서 스택의 제일 위에 X가 있고 a를 입력받으면
p라는 state로 가고 X는 감마로 바뀐다.