Constructing a PDA for $L=\{uawb\mid u,w\in\{a,b\}^*,\ |u|=|w|\}$

We want a push-down automaton (PDA) that recognizes the language $L=\{uawb\mid u,w\in\{a,b\}^*,\ |u|=|w|\}.$ So each accepted string has the form:

1. a prefix $u$ over $\{a,b\}$,
2. then one symbol $a$,
3. then a string $w$ over $\{a,b\}$,
4. then one symbol $b$,

with the constraint that the length of $u$ equals the length of $w$.

Key terms: pushdown automaton , stack alphabet , stack discipline , configuration.

High-level construction idea

Use the stack to count (in unary) how many symbols are in $u$.

• While reading the prefix $u$ (unknown length), push one stack symbol per read input symbol.
• When the PDA decides it has reached the middle symbol $a$, it switches to a “matching” phase where it reads the $w$ part and pops one stack symbol per symbol of $w$.
• Finally, after $w$ is fully matched (stack empty), it must read the last symbol $b$ and accept.

This works because “$|u|=|w|$” is exactly the condition “we popped once for each symbol pushed.”

The PDA will be nondeterministic about where $u$ ends (i.e., where it decides to read the distinguished middle $a$).

Formal PDA definition

We construct a PDA $M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ that accepts by final state.

• $\Sigma=\{a,b\}$
• $\Gamma=\{Z_0,X\}$ where:
  • $Z_0$ is the initial stack bottom marker
  • $X$ is used as one “unit” per symbol of $u$
• $Q=\{q_{\text{push}},q_{\text{pop}},q_{\text{accept}}\}$
• Start state: $q_0=q_{\text{push}}$
• Initial stack symbol: $Z_0$
• Final states: $F=\{q_{\text{accept}}\}$

We define $\delta$ by transitions (below). Notation: $\delta(q,\,\text{input},\,\text{top}) \ni (q',\,\text{stack action})$.

Transition function $\delta$

We now list transitions that implement the above behavior.

1) Push phase: $q_{\text{push}}$

For $s\in\{a,b\}$:

• $\delta(q_{\text{push}}, s, Z_0)\ni (q_{\text{push}}, XZ_0)$
• $\delta(q_{\text{push}}, s, X)\ni (q_{\text{push}}, XX)$

These transitions push one $X$ for every consumed symbol of $u$.

2) Guess the middle $a$: switch to pop phase

On reading the distinguished middle symbol $a$, do:

• $\delta(q_{\text{push}}, a, Z_0)\ni (q_{\text{pop}}, Z_0)$ (allowed only if $u$ could be empty)
• $\delta(q_{\text{push}}, a, X)\ni (q_{\text{pop}}, X)$

Interpretation: we consume that $a$ but do not pop anything at the boundary; we only pop during the $w$ phase.

3) Pop phase: match length of $w$ to length of $u$

For $s\in\{a,b\}$:

• $\delta(q_{\text{pop}}, s, X)\ni (q_{\text{pop}}, \epsilon)$

This pops one $X$ per symbol of $w$.

4) After $w$, require stack empty (top is $Z_0$) and read final $b$

• $\delta(q_{\text{pop}}, b, Z_0)\ni (q_{\text{accept}}, Z_0)$

This ensures:

• we have consumed the final $b$,
• and the stack has no remaining $X$ (so $|u|=|w|$).

Why this PDA recognizes exactly $L$

Soundness ($\Rightarrow$):
Assume $M$ accepts some string. Acceptance requires reaching $q_{\text{accept}}$ via the transition that consumes the final $b$ when the stack top is $Z_0$. That implies:

• all $X$ pushed during reading $u$ have been popped during reading $w$, so $|u|=|w|$,
• exactly one middle symbol $a$ was consumed to switch from push to pop,
• and the last consumed symbol is $b$. Thus the input is $uawb$ with $u,w\in\{a,b\}^*$ and $|u|=|w|$.

Completeness ($\Leftarrow$):
Given any string $uawb$ with $|u|=|w|$, the PDA can:

• push one $X$ per symbol in $u$,
• nondeterministically choose the correct position of the middle $a$ (the one shown),
• then pop one $X$ per symbol of $w$,
• and finally read the ending $b$ when stack top is $Z_0$. So the PDA has an accepting run.

Key terms: nondeterminism , acceptance by final state , unary counting with stack.

Visual summary (state machine view)