Zapoctove priklady Pavel Surynek chutovky

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Zapoctove priklady Pavel Surynek chutovky

Příspěvek od lickra »

Zadani od Surynka na zapoctove pisemky( http://ktiml.mff.cuni.cz/~surynek/teach ... 5-2008.pdf )
1)
Dána gramatika G = (VT ,VN ,S,P), kde V= {a,b}, VN = {S, A,B,C,D} a P = {S -> aSbA |lambada ; A -> aBbA| bCB |CD;B -> bbBa | aS;C -> aAaA|lambada ;D -> SC | aABb}. Je gramatika G kontextová? Je jazyk generovaný gramatikou G kontextový? Pokud ano, napište ekvivalentní kontextovou gramatiku.

-- kontextova neni lebo S->lambada a vyskytuje se na prave strane a pak C->lambada!.


2)Navrhněte zásobníkový automat přijímající jazyk L nad abecedou X = {a,b,c}, kde L={ucv|u,v \in {a,b}* &u!=v}.

3)Navrhněte gramatiku, která generuje jazyk L nad abecedou X = {a,b}, kde L={a^pb^q|p,q jsou prvočísla & p ≠ q}. Lze vůbec tento úkol splnit?

--gramatika generuje slova s jistou pravidelnosti, kdezto prvocisla jsou rozdelena nerovnomerne (nebo zatim neobevil nejakou obecnou pravidelnost) -> takova gramtika neexistuje?

Sedi? Ma nekdo jine reseni?
lj8
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 3. 6. 2007 18:23
Typ studia: Kombinace Informatika - Matematika

Re: Zapoctove priklady Pavel Surynek chutovky

Příspěvek od lj8 »

Myslim, ze se s nim o tom po pisemce nekdo bavil a rikal, ze ten ukol splnit jde, protoze to, ze je cislo prvocislem, zjistim Pascalem ~ Turinguv stroj (tuhle uvahu uz jsem nekolikrat slysel, jen ji moc neverim :) ) a Turinguv stroj -> jazyky typu 0.
ansh2

Re: Zapoctove priklady Pavel Surynek chutovky

Příspěvek od ansh2 »

Neviete ako je to s tym, ked niekto nesplna aktivitu a ma obe testy + dochadzku? Skusal sa niekto dohodnut?
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Zapoctove priklady Pavel Surynek chutovky

Příspěvek od Kubees »

Ja nechodil na cviceni vubec a Surynek pozadoval vypracovani ukolu ke cvicenim ze stranky Romana Bartaka jako nahradu za dochazku a aktivitu. Mel jsem to ale domluvene od zacatku semestru.
thoth
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 4. 6. 2009 14:32
Typ studia: Informatika Bc.

Re: Zapoctove priklady Pavel Surynek chutovky

Příspěvek od thoth »

Caute,
neviete, ako na tento priklad z dnesnej pisomky? Mali ste to niekto?

3) Navrhnite gramatiku, ktora generuje jazyk L nad abecedou X = {a}, kde L = {a^(x^3) | x = 0, 1, 2 ... }.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“