[Zk] 17. 5., 15:00

Pisemka byla skutecne mnohem lehci, nez jsem cekal. Kdo se obcas ukazal na cviceni a precetl si zbezne slajdy, musel snad k vetsine prikladu neco napsat. ;-)

Bylo patnact otazek, z avizovanych dvou hodin se ale nakonec vyklubalo efektivne pouze hodina a trictvrte. Pro mne osobne velice frustrujici byl malinky prostor na odpovedi na papire, kam se (drouboulinkym pismem) odpoved jen tak tak vesla, a kdyz jste nekde udelali chybu a prepisovali ji, uz v tom zacinal byt gulas. Je asi dobre si zvlaste veci jako konstrukce regularnich vyrazu nejdrive nacrtnout na nejaky auxiliary papir.

Co si tak pamatuji z varianty B:

Definujte formalni generativni gramatiku

Napiste definicni obor a obor hodnot prechodove funkce zasobnikoveho automatu

Definujte jazyk L^i

Jsou-li dva automaty ekvivalentni, jsou i isomorfni? (a definujte ekvivalenci a isomorfismus)

Urcete (a dokazte), zda pro jazyky L_1,L_2,L_3 plati L_1(L_2 prunik L_3)=L_1L_2 prunik L_1L_3

Urcete (a dokazte), zda je jazyk {1^k 1^k 0^l | k,l >= 0} regularni (ty dve k-cka nejsou preklep)

Uvedte dve ekvivalentni charakteristiky kontextovych jazyku a dokazte onu ekvivalenci

Formalne popiste algoritmus, ktery pro dva jazyky L_1, L_2 zjisti, zda L_1 prunik L_2 = \emptyset

Sestrojte zasobnikovy automat, ktery pro abecedu {0,1}, kde 0 je leva zavorka a 1 prava zvorka, rozpozna spravna uzavorkovani. Muze byt automat deterministicky?

Sestrojte regularni vyraz k zadanemu automatu (byl zadany schematem, trojstavovy, ale s hromadou prechodu)

Pro zadanou (jednoduchou, tripravidlovou) bezkontextovou gramatiku sestrojte zasobnikovy automat, ktery ji rozpoznava.

Rozhodnete (a dokazte), zda jsou dva konecne automaty (zadane tabulkou) ekvivalentni

... vypada to, ze tri uz si nepamatuju. :(

Jo, opravdu to bylo jednoduché. Prolezl bych i bez učení. Pokusím se napsat, co tam bylo za otázky. Celkem jich bylo 15 a měli jsme 2 hodiny (čili od 15:30 do 17:00).

1. Definice formální generativní gramatiky.

2. Definiční obor a obor hodnot přechodové funkce zásobníkového automatu.

3. Určete (a dokažte), zda je jazyk {1^k 0^k 1^l | k,l >= 0} regulární
   -> snadno z pumpovacího lemmatu

4. Dokončit definici zřetězení jazyků L1.L2 = { w | ...

5. Určete a dokažte, jestli pro libovolné dva jazyky L1 a L2 platí (L1 průnik L2)* = L1* průnik L2*.
   -> zkusme zvolit L1 = {aa} a L2 = {aaa}

6. Sestrojte zásobníkový automat, který pro abecedu {0,1}, kde 0 je levá závorka a 1 pravá závorka, rozpozná správná uzávorkování prázdným zásobníkem. Může být automat deterministický?
   -> deterministický být nemůže, bo je prefixový. Samotný automat je jednoduchý.

7. Zadán čtyřstavový nedeterministický konečný automat. Určete všechny stavy, do kterých se automat může dostat po přečtení libovolného slova délky dvě. Pro všechna tato slova určete, jestli je automat přijímá nebo ne.

8. Zadán třístavový automat obrázkem, určete regulární výraz, jehož hodnotou je jazyk popsaný zadaným automatem.
   -> rychle šlo odpozorovat, že výsledek je (ab)*

9. Zadány dvě gramatiky, je třeba charakterizovat oba jazyky generované gramatikami a pak také jejich průnik
   G1:
   S => AB
   A => aAb | lambda
   B => cB | lambda
   ...L1 = {a^i b^i c^j | i,j >= 0}

G2:
S => BC
B => aB | lambda
C => bCc
...L2 = {a^i b^j c^j | i,j >= 0}
...L1 průnik L2 = {a^i b^i c^i | i>=0}

10. Určit, zda jsou dva automaty ekvivalentní. Oba zadány tabulkou, oba osmistavové. Bylo to jednoduché, stačilo je nakreslit a bylo vidět, že jsou to šestistavové kružnice.

11. Určete a dokažte, zda jsou rekurzivně spočetně jazyky uzavřené na doplněk.
    -> Tenhle jsem neměl, nicméně nejsou.

12. Navrhněte konečný automat, který by přijímal slova z abecedy {a, b}, která mají počet znaků 'a' dělitelný třemi, ale ne dělitelný dvěma.
    -> Jednoduše automat, který přijímá slova s počtem znaků 'a' rovným 6k+3 pro k >= 0.

13. Určit a dokázat, zda lze každý jazyk rozpoznatelný konečným automatem zapsat formou regulárního výrazu.
    -> Takové ty věci, že všechny regulární jazyky se dají poskládat z jednopísmenkových pomocí sjednocení, zřetězení a iterace, to pak lze zapsat regulárními výrazy a asi by to chtělo nějakou indukci.

Číslování je tady jenom pro oddělení úloh, na písemce bylo jiné. Vypadá to, že na dvě úlohy jsem si nevzpomněl.

tak to mi snad ani nerikejte, sem se skrtnul jen proto, ze sem nestihnul posledni prednasku a pul, a jak se zda tak to tam nedal:(, leda ze by to byly ty zapomenuty priklady.

hippies wrote:tak to mi snad ani nerikejte, sem se skrtnul jen proto, ze sem nestihnul posledni prednasku a pul, a jak se zda tak to tam nedal:(, leda ze by to byly ty zapomenuty priklady.

no bzlo tam jednou sestrojit turinguv stroj, isce na regularnigramatiku, ale chtel to turingem

Byl tam i Postup korespondecni problem, ale dalo se to nejak...umlatit...ale daval tam i takove veci.

tak to ste me uklidnili:)

No teda pokud me pamet nesali opravdu hodne, tak konkr. v Bcku nebylo z poslednich dvou prdnasek vubec nic (snad krome tech charakteristik kontextovych automatu, jak bylo v tech otazkach vyse). Mam pocit, ze ty zapomenute otazky se nijak nevymykaly obtiznosti ani zamerenim...

Co se skupiny C týče, tak tam z posledních dvou přednášek byla jenom úloha o uzavřenosti rekurzivně spočetných jazyků na doplněk, na kterou jsem si vzpomněl. Ty dvě zapomenuté se týkaly něčeho snadného.

pasky wrote:Urcete (a dokazte), zda je jazyk {1^k 1^k 0^l | k,l >= 0} regularni (ty dve k-cka nejsou preklep)

Nevi nekdo, jak se delalo tohle? Dik.

twoflower wrote:

pasky wrote:Urcete (a dokazte), zda je jazyk {1^k 1^k 0^l | k,l >= 0} regularni (ty dve k-cka nejsou preklep)

Nevi nekdo, jak se delalo tohle? Dik.

Dalo se to asi delat ruzne exoticky spoustou metod (z definice regularity, podle ruznych vet a ekvivalenci...), ja na to sel tak, ze podle Kleena v tom pripade existuje konecny automat, tak jsem ten konecny automat sestrojil. ;-) Ten jazyk je jednoduchoucky, je to vlastne sudy pocet jednicek nasledovany libovolnym poctem nul. Jeste to chce asi dokazat, ze ten automat prijima prave tenhle jazyk, ale to je take jednoduche - ted nevim, jak jsem to delal, doufam, ze jsem na to nezapomnel, ale asi to pujde snadno sporem i indukci...

noo...nechci ti do toho kecat, ale z pumping lemmatu vyplyva, ze to regularni neni. Staci vzit slovo, kde k>n a pripumpovat jednu 1. Potom napumpovane slovo bude ve tvaru 1^(k+1) 1^k 0^l. A tohle slovo do zadaneho jazyka proste nenacpes.

Vidlák wrote:noo...nechci ti do toho kecat, ale z pumping lemmatu vyplyva, ze to regularni neni. Staci vzit slovo, kde k>n a pripumpovat jednu 1. Potom napumpovane slovo bude ve tvaru 1^(k+1) 1^k 0^l. A tohle slovo do zadaneho jazyka proste nenacpes.

Pravda, dik :) Ja to zkousel z Nerodovy vety a nejak jsem to v tom nevidel.

nerekl bych / pumping lemma (pokud se nemzlim :twisted: ) nerika jak velka je pumpovaci cast - kolik ma znaku... takze pokud ma sudy pocet jednicek, neni problem pumpovat... :wink:

Lada wrote:nerekl bych / pumping lemma (pokud se nemzlim :twisted: ) nerika jak velka je pumpovaci cast - kolik ma znaku... takze pokud ma sudy pocet jednicek, neni problem pumpovat... :wink:

Hm, sakris, to je fakt. A je to regularni vyraz

(11)0

je to i na modrym.

mno.. ja mu proste nakreslil automat, ktery to slovo prijme a napsal ze regularni automat prijima regularni jazyky... tecka

jinak ten automat je

      | 0 | 1
-------------
<-> 1 | 2 | 3
<-  2 | 2 | 4
    3 | 4 | 1
    4 | 4 | 4