Answer

Language: $L = \{ W W^r \mid W \in \{a,b\}^* \}$ — even-length palindromes over $\{a,b\}$.

$W^r$ = reverse of $W$. Examples: $\epsilon$, $aa$, $bb$, $abba$, $baab$, $aabbaa$, …

---

PDA Design (NPDA)

This language is not deterministic (NPDA needed) — the PDA must guess the midpoint.

PDA: $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$

• $Q = \{q_0, q_1, q_2\}$
  • $q_0$: reading first half, pushing symbols
  • $q_1$: reading second half, popping & matching
  • $q_2$: accept (final state)
• $\Sigma = \{a, b\}$
• $\Gamma = \{a, b, Z_0\}$ ($Z_0$ = bottom marker)
• $q_0$ = start
• $F = \{q_2\}$ (final state)
• Empty stack also accepted: $Z_0$ remains at bottom, all input symbols pushed then popped

---

Transition Function $\delta$

Current State	Input	Stack Top	Action	Next State	Push/Pop
$q_0$	$a$	$X \in \{a,b,Z_0\}$	Push $a$	$q_0$	$a$
$q_0$	$b$	$X$	Push $b$	$q_0$	$b$
$q_0$	$\epsilon$	$X$	Guess midpoint, switch to pop	$q_1$	$\epsilon$ (no change)
$q_1$	$a$	$a$	Pop & match	$q_1$	$\epsilon$ (pop)
$q_1$	$b$	$b$	Pop & match	$q_1$	$\epsilon$ (pop)
$q_1$	$\epsilon$	$Z_0$	All matched, stack = $Z_0$	$q_2$	$\epsilon$

Formally:

• $\delta(q_0, a, X) = \{(q_0, aX)\}$ for $X \in \{a,b,Z_0\}$
• $\delta(q_0, b, X) = \{(q_0, bX)\}$ for $X \in \{a,b,Z_0\}$
• $\delta(q_0, \epsilon, X) = \{(q_1, X)\}$ for $X \in \{a,b,Z_0\}$ (midpoint guess)
• $\delta(q_1, a, a) = \{(q_1, \epsilon)\}$
• $\delta(q_1, b, b) = \{(q_1, \epsilon)\}$
• $\delta(q_1, \epsilon, Z_0) = \{(q_2, \epsilon)\}$

---

State Diagram

         a,b / X → aX,bX
      ┌───────────────────┐
      ▼                   │
  (q0)──ϵ, X/X──►(q1)──a/a:pop,b/b:pop──►(q1)
      │               │
      │               ϵ, Z0/ϵ
      │               ▼
      └──────────────►(q2)  [Accept]

---

How It Works (Example: $W=ab$ → $abba$)

1. Push phase ($q_0$):

   • Read a, push a: stack = a Z0
   • Read b, push b: stack = b a Z0
   • Guess midpoint ($\epsilon$): go to $q_1$, stack unchanged b a Z0

2. Pop phase ($q_1$):

   • Read b, top=b → pop → stack = a Z0
   • Read a, top=a → pop → stack = Z0
   • Input exhausted, $\epsilon$-transition on $Z_0$ → $q_2$

3. Accept: $q_2 \in F$, or stack = $Z_0$ (empty-stack acceptance).

---

Acceptance Modes

Mode	Condition
Final State	Reach $q_2 \in F$
Empty Stack	After reading all input, stack = $Z_0$ (all pushed symbols matched and popped, only $Z_0$ remains)

Both equivalent here; PDA accepts by both.

---

Why Nondeterministic?

• The $\epsilon$-transition from $q_0$ to $q_1$ guesses the midpoint.
• For odd-length strings (not in $L$), no guess works → rejects.
• For $WW^r$, correct guess at exact middle → accepts.
• DPDA cannot guess midpoint deterministically → $L$ not DCFL.

---

Alternative: CFG

$S \rightarrow aSa \mid bSb \mid \epsilon$ generates $L$.

---

Final Answer

NPDA with 3 states ($q_0, q_1, q_2$):

• $q_0$: push $a,b$ onto stack while reading first half
• $\epsilon$-transition: guess midpoint, switch to $q_1$
• $q_1$: pop & match each input symbol with stack top
• $\epsilon$ on $Z_0$: accept ($q_2$)
• Accepts by final state $q_2$ and empty stack ($Z_0$ only).