Pushdown automata and properties of context free languages notes — Unit 4

A DFA cannot count because it has no memory. It cannot recognize $a^n b^n$.

To process Context-Free Languages (CFLs), we upgrade the DFA by attaching an infinite memory structure: a Stack. This new machine is a Pushdown Automaton (PDA).

⇒1.1 The Stack Mechanism

The memory is strictly LIFO (Last-In, First-Out). The machine can only read, push, or pop the absolute top symbol of the stack. It cannot look deep inside the stack.

How does a PDA solve $a^n b^n$?
1. As it reads the 'a's, it PUSHES an 'A' onto the stack for every 'a' it sees.
2. When the 'b's start, for every 'b' it reads, it POPS one 'A' off the stack.
3. When the string ends, if the stack is exactly empty, it mathematically proves the number of 'a's exactly matched the 'b's.

A Pushdown Automaton is mathematically defined as a 7-tuple:
$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$

• $Q$: A finite set of states.
• $\Sigma$: The input alphabet (the tape symbols).
• $\Gamma$ (Gamma): The Stack Alphabet. A finite set of symbols that are allowed to be pushed onto the stack. It can be completely different from $\Sigma$.
• $q_0$: The start state.
• $Z_0$: The Initial Stack Symbol. When the machine boots up, the stack is never truly empty; it contains this single bottom marker symbol. ($Z_0 \in \Gamma$).
• $F$: The set of accepting final states.

⇒2.1 The Transition Function ($\delta$)

The brain of the PDA is significantly more complex than a DFA. It makes decisions based on THREE factors:
1. The current State.
2. The current Input Symbol being read (or $\epsilon$).
3. The current symbol at the TOP of the Stack.

$\delta(q, a, X)$ outputs a set of pairs $(p, \gamma)$, meaning: "Go to state $p$, pop $X$, and push the string $\gamma$ onto the stack".

In Unit 1, we proved DFA $\equiv$ NFA. They have the exact same computing power.

This is absolutely FALSE for Pushdown Automata.

⇒3.1 DPDA vs NPDA

A Deterministic PDA (DPDA) has strictly one valid move for any combination of State, Input, and Top-of-Stack. It cannot guess.

A Nondeterministic PDA (NPDA) can guess. It can branch.

Consider the language of even-length palindromes: $ww^R$ (e.g., $abba$).
An NPDA reads the first half of the string and pushes it to the stack. Then, it magically "guesses" when the exact middle of the string is reached, and switches modes to start popping and matching the reverse half.
A DPDA cannot guess where the middle is. It fails.

Crucial Theorem: NPDA is mathematically MORE POWERFUL than DPDA. Therefore, "PDA" by default always refers to the nondeterministic version. DPDAs define a smaller sub-class of languages (Deterministic Context-Free Languages, which are used to build LR parsers).

A DFA accepts a string if it ends in a Final State. Because a PDA has two components (State and Stack), it has two completely different, mathematically equivalent ways to accept a string.

⇒4.1 Acceptance by Final State

The standard way. The machine processes the entire input string. If, after the last character is read, the machine is physically located inside a state belonging to the set $F$, the string is accepted. We completely ignore whatever garbage might be left on the stack.

⇒4.2 Acceptance by Empty Stack

The machine processes the entire input string. We completely ignore what state the machine is in (the set $F$ is irrelevant and usually empty).
If, after reading the last character, the machine pops the final $Z_0$ bottom marker, leaving the stack absolutely, perfectly empty, the string is accepted.

Theorem: These two acceptance methods are mathematically equivalent. An algorithm exists to convert a Final-State PDA into an Empty-Stack PDA, and vice versa.

Just as Kleene's Theorem linked RE to DFA, there is a fundamental theorem linking grammars to stack machines:

Theorem: A language is Context-Free if and only if it is accepted by some Pushdown Automaton.
CFG $\equiv$ PDA.

⇒5.1 Converting CFG to PDA

We can mechanically build an Empty-Stack PDA that acts as a "Top-Down Parser" to simulate any CFG.

The PDA has only ONE single state ($q$).
1. Push the Start Symbol $S$ onto the stack.
2. For every production rule $A \rightarrow \alpha$, add a $\epsilon$-transition: $\delta(q, \epsilon, A) = (q, \alpha)$. (This allows the PDA to magically expand variables on the stack).
3. For every terminal symbol 'a', add a matching transition: $\delta(q, a, a) = (q, \epsilon)$. (If the top of the stack matches the input character, pop it to consume the input).

We know $a^n b^n$ is context-free. But what about $a^n b^n c^n$?
A PDA has only one stack. If it pushes 'A's to count the 'a's, and pops them to match the 'b's, the stack is now empty. It has completely forgotten the count $n$, and cannot verify the 'c's.
Therefore, $a^n b^n c^n$ is NOT context-free.

To prove this mathematically, we use the advanced Pumping Lemma for CFLs.

⇒6.1 The Theorem Statement

If $L$ is a CFL, there exists a pumping length $p$. Any string $w in L$ where $|w| \ge p$ can be split into exactly FIVE pieces:
$w = uvxyz$

Satisfying three strict conditions:

• 1. $|vy| > 0$: You must pump at least one character. Either $v$ or $y$ (or both) must not be empty.
• 2. $|vxy| \le p$: The middle three pieces combined must be shorter than the pumping length.
• 3. For all $i \ge 0, uv^ixy^iz \in L$: You must pump $v$ and $y$ simultaneously, the exact same number of times, and the resulting string must remain in the language.

⇒7.1 Prove $L = \{a^n b^n c^n\}$ is not context-free.

• Step 1: Assume $L$ is a CFL. Let $p$ be the pumping length.
• Step 2: Choose string $w = a^p b^p c^p$. (Length is $3p$, which is $\ge p$).
• Step 3: The lemma states $w = uvxyz$, and $|vxy| \le p$.
  Because the "pumpable window" $vxy$ has a maximum length of $p$, it is physically impossible for this window to span across all three letters ('a', 'b', and 'c').
  The window can contain only 'a's, only 'b's, only 'c's, or straddle the boundary of 'a/b' or 'b/c'. It absolutely CANNOT contain both 'a's and 'c's.
• Step 4: Pump the string: $uv^2xy^2z$.
  Because $v$ and $y$ do not contain all three letters, pumping them will increase the count of one or two letters, but NOT the third.
  (e.g., if the window was in the 'a's, we now have more 'a's than 'b's or 'c's).
• Step 5: The pumped string loses its $n=n=n$ balance. It is impossible for $uv^2xy^2z$ to be in $L$.

Conclusion: Contradiction achieved. The language is NOT context-free.

Unlike Regular Languages (which are practically indestructible), Context-Free Languages are incredibly fragile. Because of the nature of the single stack, they break under many standard mathematical operations.

⇒8.1 Operations where CFLs are CLOSED (Safe)

If $L_1$ and $L_2$ are CFLs, the following are guaranteed to be CFLs:

• Union: $L_1 \cup L_2$. (Create a new start symbol $S \rightarrow S_1 \mid S_2$).
• Concatenation: $L_1 \cdot L_2$. (Create a new start symbol $S \rightarrow S_1 S_2$).
• Kleene Star: $L_1^*$. (Create a new start symbol $S \rightarrow S_1 S \mid \epsilon$).

⇒8.2 Operations where CFLs are NOT CLOSED (Unsafe)

If $L_1$ and $L_2$ are CFLs, the following are NOT guaranteed to be CFLs:

• Intersection: $L_1 \cap L_2$ is NOT closed.
  Proof: Let $L_1 = \{a^n b^n c^m\}$ (CFL, stack matches a/b, ignores c).
  Let $L_2 = \{a^m b^n c^n\}$ (CFL, stack ignores a, matches b/c).
  The intersection is $\{a^n b^n c^n\}$. We just proved using the Pumping Lemma that this is NOT a CFL.
• Complement: $\overline{L}$ is NOT closed.
  Proof: By De Morgan's Law, $L_1 \cap L_2 = \overline{ \overline{L_1} \cup \overline{L_2} }$. If CFLs were closed under complement, then because they are closed under union, they would HAVE to be closed under intersection. We just proved they aren't.

Unit 4 merges the algebraic grammars of Unit 3 into the physical machine world.

⇒9.1 University Exam Checklist

• Write the formal 7-tuple definition of a Pushdown Automaton. Explain the role of $\Gamma$ and $Z_0$.
• Explain the difference between DPDA and NPDA. Why is NPDA more powerful?
• What are the two methods of acceptance for a PDA? Are they equivalent?
• Draw a complete PDA state diagram (or write the $\delta$ transition functions) for the language $L = \{a^n b^n \mid n \ge 1\}$.
• Draw a PDA for the language of even-length palindromes $ww^R$. (Requires non-determinism).
• Explain the algorithmic process to convert a Context-Free Grammar directly into an Empty-Stack PDA.
• State the Pumping Lemma for Context-Free Languages, detailing the 5-part split $uvxyz$.
• Use the CFL Pumping Lemma to mathematically prove that $L = \{a^n b^n c^n\}$ and $L = \{ww\}$ (copy language) are NOT context-free.
• List the closure properties of Context-Free Languages. Prove mathematically why CFLs are NOT closed under Intersection.