Prikladiky
- xstyler
- Matfyz(ák|ačka) level II
- Příspěvky: 66
- Registrován: 29. 1. 2005 12:27
- Typ studia: Informatika Bc.
- Bydliště: EU
Prikladiky
Zdravim. Pozeral som na testove otazky z automatov a na nasledovne neviem najst odpoved. Tak keby niekto vedel, nech pls napise. Dik
1. Uvedte dve ekvivalentni charakteristiky kontextovych jazyku a dokazte onu ekvivalenci.
2. Formalne popiste algoritmus, ktery pro dva jazyky L_1, L_2 zjisti, zda L_1 prunik L_2 = emptyset
3. Určete a dokažte, zda jsou rekurzivně spočetně jazyky uzavřené na doplněk
1. Uvedte dve ekvivalentni charakteristiky kontextovych jazyku a dokazte onu ekvivalenci.
2. Formalne popiste algoritmus, ktery pro dva jazyky L_1, L_2 zjisti, zda L_1 prunik L_2 = emptyset
3. Určete a dokažte, zda jsou rekurzivně spočetně jazyky uzavřené na doplněk
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 18. 1. 2005 15:15
- Typ studia: Informatika Mgr.
- Bydliště: Brno / 17. Listopad
- Kontaktovat uživatele:
Re: Prikladiky
1) no rek bych, ze prvni charakteristika je, ze pro ne existuje kontextova gramatika a druha, ze existuje nezkracujici gramatika (dukaz viz slidy)xstyler píše: 1. Uvedte dve ekvivalentni charakteristiky kontextovych jazyku a dokazte onu ekvivalenci.
2. Formalne popiste algoritmus, ktery pro dva jazyky L_1, L_2 zjisti, zda L_1 prunik L_2 = emptyset
3. Určete a dokažte, zda jsou rekurzivně spočetně jazyky uzavřené na doplněk
2) no nevim, to je pro obecne jazyky? napada me setridit si slova ktera obsahuji podle jejich delky a podle abecedy a pak tyto dva seznamy porovnat. Ale treba turignovym strojem to takto rozhodnout nejde, kdyz jsou jazyky nekonecne, zejo... Uz problem, zda jazyky dvou BK gramatik maji neprazdny prunik je algoritmicky nerozhodnutelny - viz http://kti.ms.mff.cuni.cz/~bartak/autom ... 12_2x2.pdf
3) nejsou - viz ty stejne slidy - dukaz ze vsechny rekurzivne spocetne jazyky nejsou rekurzivni
- hydrant
- Matfyz(ák|ačka) level III
- Příspěvky: 196
- Registrován: 4. 1. 2005 12:50
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Ja si myslim o 1) toto (opravte ma ak sa mylim
Jedna charakteristyka kontextovych jazykoch je
-> kontextovy jazyk je generovany gramatikov typu 1
druhy
-> kontextovy jazyk je rozpoznavany linearne omezenym automatom
do odpovede by som napisal definiciu oboch tychto veci a dokaz ze su navzajom prevoditelne... su to 2 slajdy v 12. prednaske
hydrant
Jedna charakteristyka kontextovych jazykoch je
-> kontextovy jazyk je generovany gramatikov typu 1
druhy
-> kontextovy jazyk je rozpoznavany linearne omezenym automatom
do odpovede by som napisal definiciu oboch tychto veci a dokaz ze su navzajom prevoditelne... su to 2 slajdy v 12. prednaske
hydrant
- hydrant
- Matfyz(ák|ačka) level III
- Příspěvky: 196
- Registrován: 4. 1. 2005 12:50
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
2) este by som dodal k predoslej odpovedi: Staci zotriedit podla abecedy, triedenie aj podla dlzky by posobilo obcas problemy pri porovnavani slov... (ktory pointer mam posunut?) porovnavanie je rovnake ako napr u merge sortu
a do odpovedi v pisomke by som este napisal, ze pre regularne jazyky to urcit vieme. -> z 2 reg jazykov -> 2 konecne automaty -> prienik automatov -> je nejaky koncovy stav dosazitelny <=> neprazdny prienik jazykov
a do odpovedi v pisomke by som este napisal, ze pre regularne jazyky to urcit vieme. -> z 2 reg jazykov -> 2 konecne automaty -> prienik automatov -> je nejaky koncovy stav dosazitelny <=> neprazdny prienik jazykov
- hydrant
- Matfyz(ák|ačka) level III
- Příspěvky: 196
- Registrován: 4. 1. 2005 12:50
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
to je pravda teraz uz chpem ze nemmozu byt uzavrete na doplnok inak by bol kazdy rek. spoc. jazyk automaticky rekurzivny a ta veta by bola zbytocna.macbeth píše:a inak na trojku je podla mna odpoved zaporna, kedze potom by Postova veta nejak nedavala zmysel...
(L je rekurzivny <=> L a -L su rekurzivne spocetne...)
Ale aky (kde je) dokaz ktory tvrdi alebo z ktoreho vyplyva ze niesu uzavrete na doplnok?
ano idem na skusku v stredu (uz je to dnes)
-
- Admin(ka) level I
- Příspěvky: 635
- Registrován: 9. 6. 2005 12:33
- Typ studia: Informatika Mgr.
- Login do SIS: BUREJ3BM
- Bydliště: Konečně Vinohrady:)
- Kontaktovat uživatele:
No, já bych to vzal přímo z Postovy věty.
Vezmu si takový jazyk L, že je rekurzinvě spočetný, ale není rekurzivní (takový existuje, možná že by to chtělo dokázat tohle podrobněj, ale co...).
Potom dle postovy věty vím, že doplněk L není rekurzivně spočetný.
A mám protipříklad...takže nejsou uzavřené na doplněk.
Vezmu si takový jazyk L, že je rekurzinvě spočetný, ale není rekurzivní (takový existuje, možná že by to chtělo dokázat tohle podrobněj, ale co...).
Potom dle postovy věty vím, že doplněk L není rekurzivně spočetný.
A mám protipříklad...takže nejsou uzavřené na doplněk.