ZA jsou silnější než DZA
Tvrzení: Neexistuje žádný DZA Mfe přijímající:
L = {xy: x, y Î S*, y = reversal(x)}
Ilustrace:
Důkaz: Viz. str. 431 v knize [Meduna: Automata and Languages]
33/50
Třída jazyků přijímaných ZA
Třída deterministických bezkontextových jazyků¾jazyků přijímaných DZA
Ì
L = {xy: x, y Î S*, y = reversal(x)}