ZK 2009-06-23
Napsal: 23. 6. 2009 13:08
Od kamarada jsem ziskal otazky, ktere mel na "ustni" casti:
* napsat TS pro palindromy
* urcit do jaky skupiny podle Chomskeho jazyk patri a dokazat to
Zkousel jsem si to resit, kdybyste nasli chybu tak kricte:
1] Jenom slovne: Prectu prvni pismeno a ulozim si ho do stavu, na danou pozici dam specialni symbol s vyznamem "sem uz nechod". Pak bych jel s tim pismenem na konec a pokud by se schodovalo ulozene pismenko s poslednim, tak bych na tom poslednim znaku zase dal symbol "sem uz nechod". Takhle bych jezdil z jedne strany na druhou. Pokud bych dostal na konci prazdnou pasku, tak bych se prepnul do koncoveho stavu. Pokud bych narazil na spatne pismenko v prubehu prejizdeni z jedne strany na druhou, tak bych se prepnul do stavu, pro ktery neni definovana prechodova fce a tim skoncil.
Pozn. "sem uz nechod" ~ epsilon
2]
Myslenka:
1) Ukazu, ze jazyk neni regularni
2) udelam bezkontextovou gramatiku pro palindromy.
ad 1)Pro spor predpokladejme, ze jazyk je regularni. Dle Nerodovy vety existuje prava kongruence ~ konecneho indexu m na X* takova, ze L je sjednocenim jistych trid rozkladu X*/~.
Vezmu slova:
B
AB
AAB
...
A^(m+1)B
A a B jsou pismena abecedy
Dve slova padnou do stejne tridy ekvivalence (Dirichlet), oznacme je A^i.B a A^j.B (i /= j), plati pro ne tedy:
A^i.B ~ A^j.B
~ je prava kongruence, tedy ma platit:
A^i.B.A^(m-i) ~ A^j.B.A^(m-i) // pridam retezec A^(m-i) k oboum slovum
nicmene A^i.B.A^(m-i) \in L ale A^j.B.A^(m-i)
otIN L -- spor
Pozn. Pokud abeceda obsahuje pouze jedno pismeno, pak je L jiste regularni. Bezkontextovy je pro |X|>1
* napsat TS pro palindromy
* urcit do jaky skupiny podle Chomskeho jazyk patri a dokazat to
Zkousel jsem si to resit, kdybyste nasli chybu tak kricte:
1] Jenom slovne: Prectu prvni pismeno a ulozim si ho do stavu, na danou pozici dam specialni symbol s vyznamem "sem uz nechod". Pak bych jel s tim pismenem na konec a pokud by se schodovalo ulozene pismenko s poslednim, tak bych na tom poslednim znaku zase dal symbol "sem uz nechod". Takhle bych jezdil z jedne strany na druhou. Pokud bych dostal na konci prazdnou pasku, tak bych se prepnul do koncoveho stavu. Pokud bych narazil na spatne pismenko v prubehu prejizdeni z jedne strany na druhou, tak bych se prepnul do stavu, pro ktery neni definovana prechodova fce a tim skoncil.
Pozn. "sem uz nechod" ~ epsilon
2]
Myslenka:
1) Ukazu, ze jazyk neni regularni
2) udelam bezkontextovou gramatiku pro palindromy.
ad 1)Pro spor predpokladejme, ze jazyk je regularni. Dle Nerodovy vety existuje prava kongruence ~ konecneho indexu m na X* takova, ze L je sjednocenim jistych trid rozkladu X*/~.
Vezmu slova:
B
AB
AAB
...
A^(m+1)B
A a B jsou pismena abecedy
Dve slova padnou do stejne tridy ekvivalence (Dirichlet), oznacme je A^i.B a A^j.B (i /= j), plati pro ne tedy:
A^i.B ~ A^j.B
~ je prava kongruence, tedy ma platit:
A^i.B.A^(m-i) ~ A^j.B.A^(m-i) // pridam retezec A^(m-i) k oboum slovum
nicmene A^i.B.A^(m-i) \in L ale A^j.B.A^(m-i)
otIN L -- spor
Pozn. Pokud abeceda obsahuje pouze jedno pismeno, pak je L jiste regularni. Bezkontextovy je pro |X|>1