Matematické Fórum

Billy · 20. 08. 2011 20:05

Ahoj,

potreboval by som pomoct s prikladmi gramatik a jazykov, ktore dokazuju ostru inkluziu medzi jednlotlivymi triedami Chomskeho hierarchie.
Co mam zatial:
Regularne vs. bezkontextove:
$a^ib^i, 0\leq i$ - automat je trivialny + jasny dokaz cez Nerodovu vetu alebo pumping lemma

bezkontextove vs. kontextove
$a^ib^ic^i, 0\leq i$ - dokaz ze nie je bezkontextovy zas mozem spravit pomocou pumping lemma pre BKJ, to ze je kontextovy mozem ukazat tym, ze skonstruujem danu gramatiku a skontrolujem pravidla.

kontextove vs. "neobmedzene"
Tak tu sa mi nepodarilo najst ziadny rozumny priklad a ani ako dokazat, ze ide o jazyk najvyssej triedy. Vedel by mi s tymto niekto pomoct?

Dik.

Matematické Fórum

#1 20. 08. 2011 20:05

Chomskeho hierarchie

Zápatí