Zk 30.5.

Bola drsná.

Prispejem:

Nechť A = (Q,X,delta,S,F) je nedeterministický konečný automat. Automat (Q,X,delta,S,Q-F) přijíma jazyk

• L(A)^R

• X^*-L(A)

• L(A)

• X^*

Hadajte, ktora bola spravna! (ziadna - proste chytak)

alebo:

Nechť ~^(i) je evivalence stavů konečného automatu po i krocích. Potom platí

• p ~^(i) q => p ~^(i+1) q

• p ~^(i+1) q => p ~^(i) q

• p ~^(i) q => pro všechna x z X delta(p,x) ~^(i) delta(q,x)

• p ~^(i+1) q => pro všechna x z X delta(p,x) ~^(i) delta(q,x)

Tu mala byt zaskrtnuta druha a stvrta.

Vela stastia 4.6. ;)

neoangin wrote:Bola drsná.

Vida, mne zrovna prisla ta pisemna cast celkem lehka. ;)
Jinak byly tam std. otazky, typu
*co je doplnek rek. spoc. jazyka (nic)
*co je A=(Q,X,d,q0,F), kde d je podmnozinou (Q x X x Q), za automat (NKA)
*kde je determinismus stejne silny jako ned. (KA,TS)
*L je rozpoznatelny KA prave kdyz ... (Nerodovka, existuje automat A tz L(A)=L, L je hodnotou nejakeho regexpu, !!pozor, NEzaskrtnout pumping lemma!!)

nove (?) otazky: (ty ktere jsem tu nevidel)
*libovolny bezprefixovy bezkontextovy jazyk lze prijimat

• ZA kon. stavem

• ZA pr. zasobnikem

• DZA kon. stavem

• DZA pr. zasobnikem
  *co plati pro pravidla v Chom. nor. forme gramatik (jak vypadaji):

• chujovina, myslim ze to byla definice tej Gr. formy

• X -> YZ nebo X->a, kde X,Y,Z jsou neterminaly a a terminal

• neco jako aXb -> awb, kde X je neterminal, a,b jsou z (Vn U Vt)* a w je z (Vn U Vt)⁺ ... // tim w si nejsem uplne jisty

• podobne, ale w mohlo byt snad i lambda, takze to neplati
  ... tady jsem mel zaskrtnutou jen 2. moznost a bylo to blbe, z toho usuzuji, ze melo byt zaskrtle asi i to 3.

ustni cast:
Dostal jsem sestrojit redukovany KA pro jazyk, ktery obsahuje slova s 2 a vice ackama na konci, pred kterouzto skupinou je aspon 1 b. (tedy neco jako (a+b)baa(a)). Napsat def. red. automatu, def. ekvivalence a ukazat a dokazat jak se hledaji a vypousteji ekvivalentni stavy (nejake vety o tom).
Prvni cast pohodicka, v tom "ukazat a dokazat" jsem se vsak trochu zamotal, nevedel jsem poradne co psat, nakonec chtel vsechno: vse o ekvivalenci (po tech i krocich jak se to dela) a ty veci okolo <i>podiloveho automat</i>. Nevim, jestli jsem mu byl taky nesympaticky, ale dost se v tom rypal a trval na detailech (treba definici toho red. automatu mi nevzal, protoze jsem nemel definovano, co je to "nedosazitelny stav"). Trochu jsem tapal v tej ekvialenci, dokazat ze kdyz p~^kq tak p~q a tyhle veci. Asi ctyrikrat byl u me, nez se mu to libilo. Ale zas dava opravdu sanci doplnit(opravit) co tam nemas. Neni zly. :) Sice celkem ostre (skoro bych rekl az pedantsky) trva na detailech (sic nekdy podstatnych ;) ), na druhou stanu to byla podle me jedna z nejkorektnejsich zkousek co jsem zazil, pokud ne ta uplne nej. :)

Na kvize na dnes zaujala jedna otazka:
G1=(N1, T, S1, P1) , G2=(N2, T, S2, P2) su kontextove gramatiky; N1, N2 su disjunktne mnoziny neterminalov. Pre gramatiku G=( N1 u N2 u {S}, T, S, P1 u P2 u {S -> S1S2}) vzdy plati:
a) L(G) = L(G1).L(G2)
b) L(G) je podmnozinou L(G1).L(G2)
c) L(G) je nadmnozinou L(G1).L(G2)

Treba si vsimnut, ze i ked su mnoziny neterminalov disjunktne, mnozina terminalov T je rovnaka, takze rozhranie S1S2 mozu pretransformovat pravidla z P1 i z P2. Napr pravidlo z P1 moze spracovat i zaciatok S2.

Okrem toho sa objavili napr. i tieto otazky:

• definicia monotonnych gramatik

• ci derivacny strom slov w urcuje vsetky lave derivacie slova v danej gramatike

Co sa tyka uspesnosti, aspon 2 ludia nepresli kvizom.

Nuz, Myshaak, si borec, dole klobuk.

Ak toto cita niekto, kto uz bol na skuske a dostal sa k druhemu prikladu, napiste, co ste dostali, prosim.

No ja mela za tri, coz byla presne znamka, pro kterou jsem si sla, vzhledemk tomu, ze jsem neumela jediny dukaz. Co se prikladu ve druhe casti tyce, tak to jsou ty same, co jsou na modrem...
Ja mela prevod regularniho vyrazu na automat + formulovat a dokazat vsechny vety, ktere s tim souvisi...
Co jsem videla u ostatnich tak meli hodne urcovani prislusnosti jazyku do chomskeho hierarchie - ale opet vsechny priklady jsou na modrem dokonce vyresene - jediny rozdil je v te teorii, tu uz mate proklepnutou z testu, takze z teorie chce vsechno, co se tyka vaseho prikladu.
Jinak dojem asi takovy, ze pokud prezijete ten test a docela nervy drasajici pohled na to, jak vam ho Bartak opravuje (a nachazi vic chyb, nez byste chteli:)), tak uz se to na tri udelat da, pokud umite vyresit nejaky ten priklad.
Taky je pravda, ze na vysledku testu docela zalezi, ja mela 20 bodu a myslim, ze kdybych jich mela o 5 vic, tak mi to, co jsem napsala u prikladu a teorie stacilo na dvojku.
Jinak souhlasim s tim, ze i kdyz je to drsna zkouska, tak to hodnoceni je hodne spravedlive - a taky vam Bartak vzdycky da moznost si znamku jeste zlepsit, pokud o to stojite.

Co se prikladu ve druhe casti tyce, tak to jsou ty same, co jsou na modrem...

co prosim te myslis tim modrym? diik

themish wrote:

Co se prikladu ve druhe casti tyce, tak to jsou ty same, co jsou na modrem...

co prosim te myslis tim modrym? diik

mff.modry.cz

napiste prosim nekdo spravnou odpoved na tu otazku, kterou sem napsal banan

dargor wrote:napiste prosim nekdo spravnou odpoved na tu otazku, kterou sem napsal banan

Správná odpověď je b), tedy L(G) je podmnožinou L(G1).L(G2).

A jses si tim prosim te jistej Petre H, protoze ngsoftware tu dal k dispozici ofoceny testy a ma tam jako spravnou odpoved zaskrtnuto ze je to nadmnozinou a ne podmnozinou ???

dargor wrote:A jses si tim prosim te jistej Petre H, protoze ngsoftware tu dal k dispozici ofoceny testy a ma tam jako spravnou odpoved zaskrtnuto ze je to nadmnozinou a ne podmnozinou ???

Já si taky myslím, že to je nadmnožina.

Máte pravdu, je to c), tedy že je nadmnožinou, špatně jsem si přečetl zadání, omlouvám se :wink:

Uz jsem si to potvrdil i na zkousce, napsal jsem nadmnozina a bylo to OK.