COMS W3261 CS Theory
Lecture 8: Pushdown Automata

1. Examples of Context-Free Grammars

1. Even-length palindromes: S → aSa | bSb | ε
2. Odd-length palindromes: S → aSa | bSb | a | b
3. Palindromes with a center marker: S → aSa | bSb | c
4. Prefix notation: E → + E E | * E E | a
5. Postfix notation: E → E E + | E E * | a
6. Balanced parentheses: S → ( S ) S | ε
7. Arithmetic expressions over id’s and num’s (ambiguous):

   E → E + E | E * E | ( E ) | id | num

8. Arithmetic expressions over id’s and num’s (unambiguous):

   E → E + T | T
   T → T * F | F
   F → ( E ) | id | num

9. Regular expressions over {a, b} (ambiguous):

   R → R + R | RR | R* | ( R ) | a | b | ε | φ

10. If-then, if-then-else statements (ambiguous):

    S → if c then S
    S → if c then S else S
    S → other_stat

2. Pushdown Automata

• A pushdown automaton is an ε-NFA with a pushdown stack (last-in, first-out stack).
• Pushdown automata are to context-free languages as finite automata are to regular languages: that is to say, pushdown automata define exactly the context-free languages.
• There are seven components to a PDA P = (Q, Σ, Γ, δ, q₀, Z₀, F):
1. Q is a finite set of states.
2. Σ is a finite set of input symbols (the input alphabet).
3. Γ is a finite set of stack symbols (the stack alphabet).
4. δ is a transition function from (Q × (Σ ∪ {ε}) × Γ) to subsets of (Q × Γ*):
• Suppose δ(q, a, X) contains (p, γ). Then whenever P is in state q, looking at the input symbol a with X on top of the stack, P may go into state p, move to the next input symbol, and replace X on top of the stack by the string γ.
• The second component, a, may be ε in which case P makes the move without looking at the input symbol and does not move to the next input symbol.
• Note that if P is nondeterministic, there may be more than one pair in δ(q, a, X). If P is nondeterministic, there may be a pair in δ(q, a, X) where a is a symbol in Σ and also a pair in δ(q, ε, X).
5. q₀ is the start state.
6. Z₀ is the start stack symbol.
7. F is the set of final (accepting) states.

3. Instantaneous Descriptions of PDA’s

• We can represent a configuration (instantaneous description) of the PDA P above by a triple (q, w, γ) where:
• q is the state of the finite-state control.
• w is the string (possibly empty) of remaining input symbols.
• γ is the string (possibly empty) of symbols on the stack. If γ = XYZ, then X is the symbol on top of the stack.
• Suppose δ(q, a, X) contains (p, α). Then to represent a single move of P using this transition we write
(q, aw, Xβ) |– (p, w, αβ)
for all strings w in Σ* and β in Γ*. Note that a may be ε.

4. The Language of a PDA

• A PDA P = (Q, Σ, Γ, δ, q₀, Z₀, F) can define a language two ways.
• Acceptance by final state: P can accept an input string w by reading all of it during a sequence of moves and entering a final state at the end.
• Formally, we define L(P), the language accepted by P by final state, to be the set of input strings w such that P can go from its initial ID (q₀, w, Z₀) in a sequence of zero or more moves to an accepting ID of the form (q, ε, α) where q is a final state and α is any stack string (perhaps empty).
• Acceptance by empty (null) stack: P can accept an input string by reading all of it and emptying its stack.
• Formally, we define N(P), the language accepted by P by empty stack, to be the set of input strings w such that P can go from its initial ID (q₀, w, Z₀) in a sequence of zero or more moves to an accepting ID of the form (q, ε, ε) for any state q.
• Note that the final states of a PDA accepting by empty stack are irrelevant.
• These two modes of acceptance are equivalent. That is, a language L has a PDA that accepts it by final state iff L has a PDA that accepts it by empty stack.

5. Deterministic Pushdown Automata

• A PDA is deterministic (a DPDA) if there is never a choice for a next move in any instantaneous description.
• More precisely, a PDA (Q, Σ, Γ, δ, q₀, Z₀, F) is deterministic if:
1. δ(q, a, X) has at most one member for any q in Q, a in Σ ∪ {ε} and X in Γ.
2. If δ(q, a, X) is nonempty for some a in Σ, then δ(q, ε, X) must be empty.
• A language that can be recognized by a DPDA is called a deterministic context-free language.
• A DPDA can recognize { wcwR | w is any string of a's and b's }.
• A PDA can recognize { wwR | w is any string of a's and b's }, but no DPDA can recognize this language.
• Thus, unlike finite automata, pushdown automata with their nondeterminism are strictly more powerful than deterministic pushdown automata.
• Note that, if L is a regular language, then L can be recognized by a DPDA.
• Since a DPDA can recognize the non-regular language { wcwR | w is any string of a's and b's }, DPDA are strictly more powerful than finite automata.

6. Practice Problems

1. Construct a PDA that accepts { wcwR | w is any string of a's and b's } by final state.
2. Construct a PDA that accepts { wcwR | w is any string of a's and b's } by empty stack.
3. Construct a DPDA that accepts { wcwR | w is any string of a's and b's } by final state.
4. Construct a PDA that accepts { wwR | w is any string of a's and b's } by final state.
5. Construct a PDA that accepts { wwR | w is any string of a's and b's } by empty stack.
6. Construct a PDA P such that N(P) = L(G) where G is S → (S)S | ε.
7. Prove that a DPDA can recognize any regular language.

7. Reading

• HMU: Ch. 6