06 PDA

PDA¶

Pushdown Automaton

NFA + Stack

Also represented as NPDA (non-deterministic)

• States \(Q\)
• Input Alphabet \(\Sigma\)
• Stack Alphabet \(\Gamma\)
  • $ marks the bottom of stack
  • Symbols are pushed/popped to/from stack
• Transitions
  • If PDA is current in state \(q_i\)
  • it reads \(a \in \Sigma_\epsilon\) off the stack
  • it pops \(b \in \Gamma_\epsilon\) off the stack

Conclusion¶

Same as NFA Conclusion

Note¶

DPDA means DFA + Stack

• Every DPDA has an equivalent PDA
• Not every PDA has an equivalent DPDA

Stack Operations¶

flowchart LR
q0((q0)) -->|"input, push → pop"| q1((q1))

CFL¶

Context-Free Language

Language that is recognized by a PDA

The intersection of 2 context-free languages does not result in another CFL

Closed Operations¶

Let \(L_1, L_2\) have grammar \(G_1 = \{S_1 \to A\}, G_2 = \{S_2 \to B\}\)

Note¶

Using properties, we can say that \(L=\{a^n b^n | n \ge 0, n \ne 50 \}\) is CFL

This is because

Non-Closed Operations¶

• Intersection is not closed \(\implies L_1 \cap L_2\) is not always CFL
• Complement is not closed \({L_1}'\) is not always CFL

PDA for CFG¶

Initialize stack as $

Leftmost Derivation¶

As pushing strings instead of a symbol into stack is not possible, we can use another approach, as both are equivalent.

flowchart LR
subgraph B
    direction LR
    p0((q0)) -->
    |"a, b → x"| p1((q1)) -->
    |"ε, ε → y"| p2((q2)) -->
    |"ε, ε → z"| p3((q3))
end

subgraph A
    direction LR
    q0((q0)) -->|"a, b → xyz"| q1((q1))
end

Classic Questions¶

PDA for \(0^n 1^n\)¶

flowchart LR
q0(((q0))) -->
|"ε, ε → $"| q1((q1)) -->
|"
0, ε → 0
(Push)
"| q1 -->
|"ε, ε → ε"| q2((q2)) -->
|"
1, 0 → ε
(Pop)
"|q2 -->
|"ε,  $ → ε"| q3(((q3)))

The reason why \(1, 0 \to \epsilon\) for \(q_2\to q_3\) can be replaced by \(\epsilon, \textcolor{hotpink}{\epsilon} \to \epsilon\) is because the top of stack should be \(\textcolor{hotpink}{\epsilon}\). The top of stack can be thought as the actual top of stack or an empty string “” \((\epsilon)\)

(Blank entries are \(\phi\))

PDA for \(ww^R\)¶

flowchart LR
q0((q0)) -->
|"ε, ε → $"| q1 -->
|"
0, $ → 0$
1, $ → 1$
0, 0 → 00
0, 1 → 01
1, 0 → 10
1, 1 → 11
(Push)
"| q1((q1)) -->
|"ε, ε → ε"| q2 -->
|"
0, 0 → ε
1, 1 → ε
(Pop)
"|q2((q2)) -->
|"ε, $ → ε"| q3(((q3)))

PDA for \(a^i b^j c^k: (i, j, k \ge 0) \land \Big((i=j) \lor (i=k) \Big)\)¶

We can simplify the regex: our PDA will accept the following strings

• \(a^i b^i c^*\)
• \(a^i b^* c^i\)

flowchart LR
q0(((q0)))
q1((q1))
q2((q2))
q3((q3))
q4((q4))
q5((q5))
q6((q6))

q0 -->
|"ε, ε → $"| q1 -->
|"a, ε → a"| q1 -->
|"ε, ε → ε"| q2 & q4

q2 -->
|"b, a → ε"| q2 -->
|"ε, ε → ε"| q3 -->
|"c, ε → ε"| q3

q4 -->
|"b, ε → ε"| q4 -->
|"ε, ε → ε"| q5 -->
|"c, a → ε"| q5 -->
|"ε, $ → ε"| q6

PDA for \(a^n b^{2n}\)¶

flowchart LR
q0(((q0)))
q1((q1))
q2((q2))
q3((q3))
q4(((q4)))

q0 -->
|"ε, ε → $"| q1 -->
|"a, ε → a"| q1 -->
|"ε, ε → ε"| q2 -->
|"b, ε → ε"| q3 -->
|"b, a → ε"| q2

q2 --> |"ε, $ → ε"| q4

PDA for \(a^{2n} b^{3n}\)¶

flowchart LR
q0(((q0)))
q1((q1))
q2((q2))
q3((q3))
q4((q4))
q5((q5))
q6(((q6)))

q0 -->
|"ε, ε → $"| q1 -->
|"a, ε → ε"| q2 -->
|"a, ε → a"| q1 -->
|"ε, ε → ε"| q3 -->
|"b, ε → ε"| q4 -->
|"b, ε → ε"| q5 -->
|"b, a → ε"|q3

q3 --->
|"ε, $ → ε"| q6

PDA for \(G = \{S \to \text{0TS1} | 1T0 , T \to 1 \}\)¶

flowchart LR
q0((q0))
q1((q1))
q2(((q2)))

q0 -->
|"&epsilon;, &epsilon; &rarr; <span style=background:yellow;color:black;font-weight:bold>S$</span>"| q1 -->
|"
&epsilon;, S &rarr; 0TS1
&epsilon;, S &rarr; 1T0
&epsilon;, T &rarr; 1
0, 0 &rarr; &epsilon;
1, 1 &rarr; &epsilon;
"| q1 -->
|"&epsilon;, $ &rarr; &epsilon;"| q2

PDA for \(G = \{S \to 0S1\} \quad (0^n 1^n)\)¶

flowchart LR
q0((q0))
q1((q1))
q2((q2))

q0 -->
|"ε, ε → S$"| q1 -->
|"
ε,  S → 1S1
0, 0 → ε
1, 1 → ε
"| q1 -->
|"ε, $ → ε"| q2

Comments