# [Zk 31. 5. 10]

<{ForumPost(poster="peci1", timestamp=2010-06-01 01:30:33)}>
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 *a*cek a zvetsi *n* o jednicku. Tot cela myslenka.  
  
S - pocatecni symbol, L - leva zarazka (soucast citace), C - soucast citace, D - signal, ze chci pridavat *a*cka, E - slouzi pro presun *a*cek vpravo a pak signalizuje, ze vsechna pozadovana *a*cka byla vytvorena a zarazena, F - rozhodli jsme se skoncit, A - prepise se ve vhodnou chvili na *a*

    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}$: 

    S=>LCCa=>FCCa=>*FFFa=>*aaaa

$a^{9}$: 

    S=>LCCa=>*LAEEDDa=>*LAEEEAEAa=>*LEEEEAAAa=>*LCCCCaaaa=>FCCCCaaaa=>*FFFFFaaaa=>*aaaaaaaaa

$a^{16}$: 

    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.
<{/ForumPost}>

<{ForumPost(poster="hroh", timestamp=2010-06-04 17:22:16)}>
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.
<{/ForumPost}>