Pushdown Automata

A Pushdown Automaton (PDA) is a computational model used to recognize Context-Free Languages (CFLs). It extends the concept of a finite automaton by adding a stack, which provides additional memory for handling nested and recursive structures, such as balanced parentheses or nested expressions.

Definition of Pushdown Automata

A PDA is formally defined as a 7-tuple (Q, Σ, Γ, δ, q₀, Z₀, F), where:

Q: A finite set of states.
Σ: The input alphabet (set of symbols).
Γ: The stack alphabet (symbols that can be pushed or popped from the stack).
δ: The transition function, defined as:
```
δ: Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*)
```
This means the PDA can transition based on the current state, input symbol (or ε for no input), and the top of the stack, and update the stack accordingly.
q₀: The start state, where the computation begins.
Z₀: The initial stack symbol, present on the stack at the start.
F: A set of accept states, where the computation ends if the PDA reaches one of these states.

A PDA accepts a string in one of two ways:

By reaching an accept state.
By emptying its stack (depending on the type of PDA).

Example 1: PDA for Balanced Parentheses

Consider the language L = {w | w contains balanced parentheses}. This language is context-free and can be recognized by a PDA.

PDA Configuration:

Q: {q₀, q₁} (start state q₀ and accept state q₁).
Σ: {‘(‘, ‘)’}
Γ: {‘(‘, Z₀} (stack alphabet includes ( and initial symbol Z₀).
Z₀: The initial stack symbol.
F: {q₁}

Transition Function (δ):

</>

Copy

δ(q₀, '(', Z₀) = {(q₀, (Z₀)}
δ(q₀, '(', '(') = {(q₀, ((}
δ(q₀, ')', '(') = {(q₀, ε)}
δ(q₀, ε, Z₀) = {(q₁, Z₀)}

Explanation: The PDA pushes ( onto the stack for every opening parenthesis and pops ( for every closing parenthesis. The string is accepted if the stack is empty after processing all input.

Example 2: PDA for Palindromes

Consider the language L = {wwᴿ | w ∈ {a, b}*}, where wwᴿ is a string followed by its reverse.

PDA Configuration:

Q: {q₀, q₁, q₂}
Σ: {‘a’, ‘b’}
Γ: {‘a’, ‘b’, Z₀}
Z₀: The initial stack symbol.
F: {q₂}

Transition Function (δ):

</>

Copy

δ(q₀, 'a', Z₀) = {(q₀, aZ₀)}
δ(q₀, 'b', Z₀) = {(q₀, bZ₀)}
δ(q₀, 'a', a) = {(q₀, aa)}
δ(q₀, 'b', b) = {(q₀, bb)}
δ(q₀, ε, Z₀) = {(q₁, Z₀)}
δ(q₁, 'a', a) = {(q₁, ε)}
δ(q₁, 'b', b) = {(q₁, ε)}
δ(q₁, ε, Z₀) = {(q₂, Z₀)}

Explanation: The PDA pushes symbols onto the stack while reading the first half of the string. When it transitions to q₁, it starts popping symbols for every matching input symbol in the second half. The string is accepted if the stack is empty at the end.

Key Takeaways

Pushdown Automata extend finite automata by adding a stack, enabling them to recognize context-free languages.
PDAs are used to recognize languages with nested or recursive structures, such as balanced parentheses or palindromes.
The stack in a PDA allows for non-linear memory, making them more powerful than finite automata but less powerful than Turing machines.
PDAs are a fundamental model for parsers in compilers and the study of formal languages.

TutorialKart

Pushdown Automata