Constructing a PDA for $L=\{a^{2n}bc\mid n\ge 0\}$ (Final State and Empty Stack)

We want a pushdown automaton (PDA) for the context-free language
$L=\{a^{2n}bc\mid n\ge 0\}.$ Intuitively: read an even number of $a$’s (possibly $0$), then match a single $b$, then a single $c$, and reject anything else.

We will build two equivalent machines:

• one that accepts by final state (using an accepting state),
• one that accepts by empty stack (by popping the entire stack).

Key notions:

• pushdown automaton (PDA)
• acceptance by final state
• acceptance by empty stack
• instantaneous description

Formally, acceptance modes are defined using the PDA’s transition relation and either an accepting state set $F$ (final state) or the condition that the stack becomes empty (empty stack). 2

Footnotes

1. Pushdown automaton - Definitions and acceptance modes (final state vs empty stack) for PDAs. ↩

2. Lecture 14 – Pushdown Automata (PDA) - COSE215 - Formal definitions of acceptance by final states and by empty stacks with illustrative PDA transition examples. ↩

Strategy to recognize $a^{2n}bc$

Use the stack to “count pairs of $a$’s”:

• For each input symbol $a$, push an $A$ onto the stack.
• When $b$ arrives, pop exactly one $A$ per previously seen $a$; but because we need even many $a$’s, we can enforce pairing by pushing per $a$ and requiring that after processing the $b$ we can only proceed if exactly the “pairing structure” allows an acceptance.

A simpler, deterministic-feeling construction is:

• while reading $a$’s, push one $A$ for each $a$,
• when $b$ is read, pop two $A$’s per “unit step” is awkward because $b$ occurs only once. Instead, we implement a standard technique: push two markers per pair of $a$’s by consuming $a$’s in pairs using an intermediate state.

Concretely:

• State $q_0$: expect the first $a$ of a pair.
• State $q_1$: after seeing one $a$ of a pair, expect the second $a$ and then push a marker $P$ representing one completed pair.
• After any number of completed pairs, transition to the $b$-reading state, then to $c$-reading state, and then accept (or empty the stack, depending on the acceptance mode).

PDA #1: Acceptance by final state

We define $M_f=(Q,\Sigma,\Gamma,\delta,q_0,Z,F)$ (a 7-tuple with accepting states $F$).

Let:

• $Q=\{q_0,q_1,q_2,q_b,q_c,q_{\text{acc}}\}$
• $\Sigma=\{a,b,c\}$
• $\Gamma=\{Z,P\}$
• start state $q_0$
• initial stack symbol $Z$
• accepting states $F=\{q_{\text{acc}}\}$

Interpretation:

• $q_0$: either begin a pair by reading the first $a$, or if no $a$’s exist ($n=0$), go directly to reading $b$.
• $q_1$: we have read exactly one $a$ of the current pair; now we must read the second $a$ to complete the pair and push $P$.
• $q_2$: we have completed $n\ge 1$ pairs; now either start another pair or go to read $b$.
• $q_b$: read exactly one $b$.
• $q_c$: read exactly one $c$.
• $q_{\text{acc}}$: accept.

Transition function $\delta$ (written as: $\delta(q,\,\text{input or }\varepsilon,\,\text{stack top})\ni (q',\,\text{stack action})$)

Key transitions:

1. Pairing $a$’s (push one $P$ per pair $aa$)

• $\delta(q_0,a,Z)\ni(q_1,Z)$

• $\delta(q_0,a,P)\ni(q_1,P)$
  (allow reading first $a$ whether stack top is $Z$ or $P$)

• $\delta(q_1,a,Z)\ni(q_2, PZ)$

• $\delta(q_1,a,P)\ni(q_2, PP)$
  (upon second $a$, push $P$ on top)

2. Move to reading $b$ after finishing $n$ pairs

• For $n=0$ (no $a$ read): from $q_0$, read $b$ with stack unchanged:

  • $\delta(q_0,b,Z)\ni(q_b,Z)$
  • $\delta(q_0,b,P)\ni(q_b,P)$
    (the $P$-case won’t be reachable for $n=0$ in a correct run, but it keeps the definition total)

• For $n\ge 1$: from $q_2$, read $b$ without changing stack:

  • $\delta(q_2,b,Z)\ni(q_b,Z)$
  • $\delta(q_2,b,P)\ni(q_b,P)$

3. Read $c$ and accept (final-state)

• $\delta(q_b,c,Z)\ni(q_{\text{acc}},Z)$
• $\delta(q_b,c,P)\ni(q_{\text{acc}},P)$

4. No other transitions allow continuation In particular, we do not provide transitions for:

• reading $a$ in $q_b$ or $q_c$,
• reading $b$ in $q_c$,
• reading any symbol after reaching $q_{\text{acc}}$.

Why this works (sketch)

• Each completed pair $aa$ pushes exactly one $P$, so runs with an odd number of $a$’s get stuck in $q_1$ waiting for the second $a$.
• After all pairs, exactly one $b$ is consumed, then exactly one $c$ is consumed.
• For $n=0$, the machine reads $b$ immediately from $q_0$, then $c$.

This recognizes precisely $a^{2n}bc$ by reaching $q_{\text{acc}}$ after consuming the input. 2

Footnotes

1. Pushdown automaton - Definitions and acceptance modes (final state vs empty stack) for PDAs. ↩ ↩²

2. Lecture 14 – Pushdown Automata (PDA) - COSE215 - Formal definitions of acceptance by final states and by empty stacks with illustrative PDA transition examples. ↩

PDA #2: Acceptance by empty stack

Now we build a PDA $M_e$ that accepts by empty stack, i.e., after consuming the entire input it reaches a configuration with empty stack (stack content $\varepsilon$). 2

Let:

• $Q'=\{q_0,q_1,q_2,q_b,q_c,q_{\text{pop}}\}$
• $\Sigma=\{a,b,c\}$
• $\Gamma'=\{Z,P\}$
• start state $q_0$
• initial stack symbol $Z$
• no accepting states needed for empty-stack acceptance (acceptance is by stack emptiness).

Transitions mirror the pair-building from $M_f$, but after reading $c$ we pop all stack symbols until empty.

1. Pair $a$’s (same logic)

• $\delta(q_0,a,Z)\ni(q_1,Z)$
• $\delta(q_0,a,P)\ni(q_1,P)$
• $\delta(q_1,a,Z)\ni(q_2,PZ)$
• $\delta(q_1,a,P)\ni(q_2,PP)$

2. After pairs, read exactly one $b$, then exactly one $c$

• $n=0$ path:

  • $\delta(q_0,b,Z)\ni(q_b,Z)$

• $n\ge 1$ path:

  • $\delta(q_2,b,Z)\ni(q_b,Z)$
  • $\delta(q_2,b,P)\ni(q_b,P)$

• $\delta(q_b,c,Z)\ni(q_c,Z)$

• $\delta(q_b,c,P)\ni(q_c,P)$

3. Empty the stack after consuming $c$ Let $q_c$ be the state that starts popping:

• $\delta(q_c,\varepsilon,P)\ni(q_c,\varepsilon)$
  (pop a $P$)
• $\delta(q_c,\varepsilon,Z)\ni(q_{\text{pop}},\varepsilon)$
  (pop bottom symbol to truly empty the stack)
• No further input should be consumed after this; because the stack becomes empty, acceptance-by-empty-stack is satisfied immediately when the computation ends.

Thus, for every string $a^{2n}bc$, the machine pushes one $P$ per $aa$ pair, consumes $b$ then $c$, and then empties the stack; for any string not in the language, it fails to reach empty stack. 2

Footnotes

1. Pushdown automaton - Definitions and acceptance modes (final state vs empty stack) for PDAs. ↩ ↩²

2. Lecture 14 – Pushdown Automata (PDA) - COSE215 - Formal definitions of acceptance by final states and by empty stacks with illustrative PDA transition examples. ↩ ↩² ↩³ ↩⁴

Visual transition logic (pairing $a$’s)