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