PDAs are Stronger than DPDAs
Theorem: There exists no DPDA Mfe that accepts
L = {xy: x, y Î S*, y = reversal(x)}
Illustration:
Proof: See page 431 in [Meduna: Automata and Languages]
33/50
The family of languages accepted by PDAs
The family of deterministic CFLs¾the languages accepted by DPDAs
Ì
L = {xy: x, y Î S*, y = reversal(x)}