Matfyz Wiki

Prikladiky

xstyler at 2006-05-30 10:17:03

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

krystof at 2006-05-30 14:40:05

xstyler wrote:

  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. no rek bych, ze prvni charakteristika je, ze pro ne existuje kontextova gramatika a druha, ze existuje nezkracujici gramatika (dukaz viz slidy)

  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 at 2006-05-30 23:47:11

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

hydrant at 2006-05-31 01:16:52

  1. 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

hydrant at 2006-05-31 01:17:53

  1. nech robim co robim, ale nechapem. Mal som ist na tu poslednu prednasku :(
    Bolo by fajn ak by sa nasiel niekto, kto to sem napise podrobnejsie

macbeth at 2006-05-31 01:24:18

Aj ty ides zajtra na skusku? :lol:

macbeth at 2006-05-31 01:27:29

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...)

hydrant at 2006-05-31 01:32:24

macbeth wrote: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...)

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.

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)

macbeth at 2006-05-31 01:37:41

tiez som ho tam nenasiel, ale mozno to je tou pokrocilou hodinou :) tak radsej idem spat...

gASK at 2006-05-31 08:31:56

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.

hydrant at 2006-06-04 19:28:21

hej tiez som na to rano pred pisomkou dosiel... tak som bol nakoniec v pohode. Mozno to chcel ale s dokazom ze rekuzivne spocetny jazyk ktory nie je rekurzivny existuje... v slajdoch ma ten dokaz akosi neformalne