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)}