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

We want a push-down automaton (PDA) that recognizes strings of the form [ u a w b \quad\text{where } u,w\in{a,b}^*\text{ and }|u|=|w|. ] This is a context-free constraint: the PDA uses its stack to “pair” each symbol of $u$ with exactly one symbol of $w$ (in reverse order) and then verifies the pairing completes exactly when the input has consumed $w$. A PDA is formally a 7-tuple $(Q,\Sigma,\Gamma,\delta,q_0,Z,F)$ with transitions that read an input symbol (or $\varepsilon$) and replace the stack top. It accepts either by reaching a final state or by emptying the stack. We will use final-state acceptance. 2

Key idea:

• Read and push the whole $u$ onto the stack (one stack symbol per input symbol of $u$).
• When the middle delimiter $a$ is read, switch to a phase where we read exactly $w$ while popping one stack symbol per symbol of $w$.
• Require that the stack is back to the bottom marker exactly when the next delimiter $b$ is read.
• Accept only if $u$ and $w$ had equal length.

We can view the workflow as a 3-phase PDA:

Keywords: pushdown automaton , stack , bottom-of-stack marker , [$\varepsilon$-transition]{def="A PDA move that consumes no input symbol"}.

Footnotes

1. Introduction of Pushdown Automata - GeeksforGeeks - Defines PDAs, stack-based recognition of context-free languages, and formal PDA notion. ↩

2. Pushdown automaton (Wikipedia) - Covers formal PDA definition and acceptance by final state or empty stack, plus transition concepts. ↩

Formal language restatement

Let $\Sigma=\{a,b\}$. The language is [ L={, u a w b \mid u\in\Sigma^,\ w\in\Sigma^,\ |u|=|w| ,}. ] So any accepted string has:

1. An $a$ delimiter at position $|u|+1$,
2. A $b$ delimiter at the end (right after $w$),
3. The number of symbols in $u$ equals the number of symbols in $w$.

This “equal-length” property is exactly what the stack can enforce: push $|u|$ items; pop one per symbol of $w$; ensure the stack returns to its initial bottom marker when $w$ ends.

Acceptance by final state is described in standard PDA definitions.

Keywords: context-free language , NPDA , accepting configuration.

Footnotes

1. Pushdown automaton (Wikipedia) - Covers formal PDA definition and acceptance by final state or empty stack, plus transition concepts. ↩

PDA $M$ for $L$

We present an NPDA that accepts by final state.

Construction

Let

• $Q=\{q_{\text{push}},q_{\text{pop}},q_f\}$
• $\Sigma=\{a,b\}$
• $\Gamma=\{A,B,Z\}$ where:
  • $Z$ is the bottom-of-stack marker,
  • $A$ and $B$ encode symbols pushed from the input (encoding details are arbitrary but explicit here).
• Start state $q_0=q_{\text{push}}$
• Initial stack symbol $Z$
• Accepting states $F=\{q_f\}$

We will include nondeterminism in when we decide to consume the middle delimiter $a$. Concretely, in the pushing phase, on reading an $a$ we may either:

• push it as part of $u$, or
• treat it as the delimiter $a$ that starts the $w$-region.

Transition function $\delta$

We use the standard PDA transition notation: [ \delta(q, x, \text{top}) \ni (q', \text{stack-replacement}) ] meaning: in state $q$, reading input symbol $x$ (or $\varepsilon$), if the stack top is $\text{top}$, then pop it and push $\text{stack-replacement}$ (possibly $\varepsilon$), move to $q'$.

(1) Pushing phase: read $u$ and push everything

In state $q_{\text{push}}$:

• On input $a$ or $b$, push an encoded symbol and stay in $q_{\text{push}}$: [ \delta(q_{\text{push}}, a, Z)\ni(q_{\text{push}}, AZ),\quad \delta(q_{\text{push}}, a, A)\ni(q_{\text{push}}, AA),\quad \delta(q_{\text{push}}, a, B)\ni(q_{\text{push}}, AB) ] [ \delta(q_{\text{push}}, b, Z)\ni(q_{\text{push}}, BZ),\quad \delta(q_{\text{push}}, b, A)\ni(q_{\text{push}}, BA),\quad \delta(q_{\text{push}}, b, B)\ni(q_{\text{push}}, BB) ]

Additionally, nondeterministically choose the delimiter:

• If the next symbol is $a$ and the current top is anything, we may instead consume that $a$ as the middle delimiter and switch to the popping phase without changing the stack: [ \delta(q_{\text{push}}, a, Z)\ni(q_{\text{pop}}, Z),\quad \delta(q_{\text{push}}, a, A)\ni(q_{\text{pop}}, A),\quad \delta(q_{\text{push}}, a, B)\ni(q_{\text{pop}}, B) ]

This nondeterminism ensures we can select the correct $a$ that is exactly after $u$.

(2) Popping phase: read $w$ while popping exactly one per symbol

In state $q_{\text{pop}}$:

• For each input symbol in $\{a,b\}$, pop one stack symbol (top can be $A$, $B$), and stay in $q_{\text{pop}}$: [ \delta(q_{\text{pop}}, a, A)\ni(q_{\text{pop}}, \varepsilon),\quad \delta(q_{\text{pop}}, a, B)\ni(q_{\text{pop}}, \varepsilon) ] [ \delta(q_{\text{pop}}, b, A)\ni(q_{\text{pop}}, \varepsilon),\quad \delta(q_{\text{pop}}, b, B)\ni(q_{\text{pop}}, \varepsilon) ]

We do not allow $a$ or $b$ to be consumed when the stack top is $Z$, because that would mean $w$ continues even though $|u|$ is exhausted. (This is what enforces $|u|=|w|$.)

(3) Final delimiter: read trailing $b$ and accept iff stack is back at $Z$

After popping exactly $|u|$ symbols, the stack top will be $Z$. Then: [ \delta(q_{\text{pop}}, b, Z)\ni(q_f, Z) ] and we accept in $q_f$ after consuming the final $b$.

This enforces the input ends right after the delimiter $b$ and that $w$ had exactly length $|u|$.

Keywords: NPDA nondeterminism , LIFO , stack encoding.

Why this PDA recognizes exactly $L$

Soundness ($M$ accepts only strings in $L$):

• The only way to leave $q_{\text{push}}$ to $q_{\text{pop}}$ is by consuming an input $a$ as the middle delimiter.
• The PDA can only consume symbols in $q_{\text{pop}}$ by popping stack symbols; hence, the number of consumed symbols of $w$ cannot exceed the number of pushed symbols from $u$.
• The only way to enter acceptance $q_f$ is by consuming a trailing $b$ while the stack top is $Z$, meaning all pushes from $u$ were popped exactly—so $|u|=|w|$. Therefore, any accepted string must be of the form $uawb$ with $|u|=|w|$.

Completeness ($M$ accepts every string in $L$):

• Given any $uawb$ with $|u|=|w|$, there exists a computation branch where the PDA:
  1. pushes exactly the characters of $u$,
  2. uses the delimiter transition on the correct $a$ after $u$,
  3. pops once per character of $w$,
  4. finally consumes the trailing $b$ when the stack is back to $Z$. This branch reaches $q_f$ and accepts.

Keywords: soundness , completeness.