[Zk 31. 5. 10]

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).
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

[Zk 31. 5. 10]

Příspěvek od peci1 »

Ahoj, par postrehu z dnesni zkousky.

Priklady v testiku mely tak 90% coverage na foru :)
Z novinek si pamatuju treba:
Bud L libovolny jazyk, potom jazyk \emptyset .L:
a) je podmnozinou L
b) je regularni
c) je nadmnozinou L
d) rovna se L
(spravne samozrejme a,b - prazdny jazyk neprijima zadne slovo (pozor - ani \lambda), takze zretezeni se nema ceho chytit a vysledkem je opet prazdny jazyk).

Pak tam bylo regularni pumping lemma, kde ale ve zneni "zapomnel" |v| > 0. Odpoved, ze plati pouze pro regularni jazyky, spravna nebyla (myslim, ze na vyber byla cela Ch. hierarchie)

Umrtnost na testu nebyla moc velka (rekl bych pod tretinu).

Z velkych prikladu jsem zaslechl napr.: \{u.u^R.u\}, \{a^ib^jc^k, i \leq j \leq k \}, \{ww\}, \{a^{n^2}\}, nekdo sestrojoval TS. Pro tyto jazyky byly rozlicne ukoly - zaradit (bez hintu, kam patri); dokazat, ze patri prave do dane tridy; sestrojit gramatiku/automat pro dany jazyk; prevest automat<->gramatiku. Plus samozrejme dokazat pouzite vety (coz ale neznamena, ze musite rekurzivne dokazat vsechna tvrzeni potrebna pro dukaz jine vety... staci se o nich treba jen zminit, napsat zneni, nebo tak).

Co se rozhodne naucte (a hlavne pochopte!) jsou dukazy pumping lemmat a Nerodovky... Na tom to stoji i pada.

Nevim, jestli to byla zvlastnost dnesni zkousky, nebo je to beznejsi jev, ale po pisemne casti nas doc. pustil pryc a sel obhajovat diplomky a obedvat... Takze jsme si mohli pred ustni casti v klidu vsechno najit :)

Mym ukolem bylo zaradit jazyk \{ a^{n^2} \}. Dukaz, ze neni bezkontextovy, najdete ve sbirce resenych prikladu na Studnici. Psal jsem tedy kontextovou gramtiku. Idea gramatiky by byla hned, ale pak jsem se hodinu paral s tim, abych opravdu mel vsechna pravidla nezkracujici a zbavil se prepisovani na lambdu.

Gramatika fungovala asi nasledovne. Kdyz si rozepisete prvnich par clenu posloupnosti n^2, je to 1, 4, 9, 16, 25... Rozdil mezi sousednimi cleny se vzdy zvysuje o dva, coz je dusledek nasledujiciho vztahu: (n+1)^2-n^2 = n^2 + 2n + 1 - n^2 = 2n + 1. Takze gramatika si drzi vlevo v "citaci" 2n+1 znaku a vzdy se rozhodne, ze je bud vsechny prepise na a, nebo vytvori 2n+1 novych acek a zvetsi n o jednicku. Tot cela myslenka.

S - pocatecni symbol, L - leva zarazka (soucast citace), C - soucast citace, D - signal, ze chci pridavat acka, E - slouzi pro presun acek vpravo a pak signalizuje, ze vsechna pozadovana acka byla vytvorena a zarazena, F - rozhodli jsme se skoncit, A - prepise se ve vhodnou chvili na a

Kód: Vybrat vše

S -> lambda | a | LCCa
LC -> LAEED //zvetsujeme n o jednicku (pridame dva znaky) + posleme vpravo signal, ze chceme pridavat
DC -> DD //posilame vpravo signal, ze chceme pridavat acka
D -> EA //vykoname prikaz pro pridani acka
AE -> EA //neni kontextove, prepiseme pomoci 4 pravidel pomoci algoritmu ze slidu; vsechna A putuji vpravo
A -> a
Ea -> Ca //vracime se do puvodniho stavu
EC -> CC

LC -> FC //rozhodneme se skoncit
FC -> FF //posilame signal o konci dale
Fa -> aa //signal o konci dorazil na konec citace, takze uz jen citac prepisu na acka
Pro nazornost derivace:
a^{4}:

Kód: Vybrat vše

S=>LCCa=>FCCa=>*FFFa=>*aaaa
a^{9}:

Kód: Vybrat vše

S=>LCCa=>*LAEEDDa=>*LAEEEAEAa=>*LEEEEAAAa=>*LCCCCaaaa=>FCCCCaaaa=>*FFFFFaaaa=>*aaaaaaaaa
a^{16}:

Kód: Vybrat vše

S=>LCCa=>*LAEEDDa=>*LAEEEAEAa=>*LEEEEAAAa=>*LEEEEaaaa=>*LCCCCaaaa=>*LAEEDDDDaaaa=>*LAEEEAEAEAEAaaaa=>*LEEEEEEAAAAAaaaa=>*
LCCCCCCaaaaaaaaa=>*FCCCCCCaaaaaaaaa=>*FFFFFFFa^9=>*a^7a^9 = a^16
Pak chtel jeste prevod na automat, tedy na LOA. Stacila napsat idea prevodu tak, jak je na slidech.

Rozdaval jednicky, dvojky i trojky (jestli nekoho od ustni vyhodil, nevim, ale spis myslim, ze ne). Vzdycky se ale ptal, co clovek chce, a kdyz chtel lepsi znamku, nez na jakou to vypadalo, tak mu dal dokazat jeste nejakou vetu nebo tvrzeni, popr. dodelat poradne/opravit dukazy z pisemne casti.
hroh
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 6. 12. 2006 13:32

Re: [Zk 31. 5. 10]

Příspěvek od hroh »

Pozn. k předchozímu přízpěvku... U toho pumping lematu nebylo "pouze" a jelikož tam chyběla podmínka |v| > 0, tak to platilo pro všechny...

Co se týče velkého příkladu, tak jsem měl vymyslet dvousměrný konečný automat, kterým bych našel slova jazyka L = { u | uuR je z jazyka L(A)}, kde A je nějaký konečný automat a uR je opačné k u. To bylo v celku jednoduché, stačilo mírně modifikovat příklad na 2KA z přednášky. Pak chtěl ještě definovat a dokázat vztah mezi jazyky přijíímanými KA a 2KA.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“