# [Zk] 29.5.

<{ForumPost(poster="Pz", timestamp=2007-05-29 15:07:31)}>
Tak v prvni casti test na 29 otazek, alespon 19 spravne (nicmene Bartak dal sanci i tem co meli 17 ci 18 bodu).  
  
Otazky jsem tu uz nekde nasel, typu   
  
L1 = {a}, L2 = {b}, jake slova patri do (L1 u L2)* (spravne vsechny   
moznosti..  
  
Vesmes nic tezkeho, kde jsem naletel ja:  
  
Prunik bezkontextoveho jazyka a regularniho je BEZKONTEXTOVY jazyk (napr. 0^i1^i je BKJ, 0^i1^j je RJ, jejich prunik je opet O^i1^i, tedy BKJ).   
  
Definoval kartezsky soucin dvou konecnych automatu a prijimaci stavy F = F1 x F2 (prijimaci stavy), coz znamena, ze se prijima prunik dvou jazyku (ja zaskrtnul sjednoceni, staci si uvedomit, co F1 x F2 znamena).  
  
Co mohou byt listy v derivacnim stromu? (fakt: jsou to prvky Vt nebo lambda).  
Moznosti byly slova Vt*, slova Vn*, symboly Vt, a tusim symboly Vn.  
Pochopil jsem to, ze pokud alespon nejaky prvek z mnoziny to splnuje, tak mnozinu zaskrtnem (cili jsem dal Vt*, Vn* a Vt, prvni dva maji lambdu, Vt ma terminaly). Spravne vsak melo byt pouze Vt, Bartak to mysli, ze vsechny prvky muzou byt v listu, nicmene kdyz jsem mu vysvetlil, jak jsem to myslel, rekl ze ok.  
  
Co si dal vzpominam:  
  
Doplnek rekurzivne spocetneho jazyka nevime co je, ale neni to nic z moznosti :)  
  
Kdyz se obrati hrany v NKA, neziska se doplnek jazyka. Co se ziska, to vi Zeus, opet nebyla spravne zadna z moznosti (bacha, u DKA to tusim plati..).  
  
Dvoucestny automat prijima totez co KA a NKA (jen dve moznosti, obe spravne).  
  
Nedeterminismus nezvysi silu u KA a TS, zvysi u ZA.  
  
Zadany automat, a do kterych stavu se da dostat pri PRIJIMAJICIM VYPOCTU PRI SLOVE Z JAZYKA AUTOMATU pri nacteni prvnich dvou pismen? Tady chytacek, ze ctyr stavu byl B koncovy neprijimaci (nevedly z nej hrany), takze pri prijimacim vypoctu se do nej nikdy nemuzem dostat (pak by se slovo neprijalo), zbyle stavy A,B a D sly.  
  
a tak podobne, snad nekdo doda vic, urcite je fajn vedet, na co si dat pozor.  
  
Co vim tak asi 3 lidi ze 14 nedali pisemku.  
  
Na ustni vim o 4 co leteli, ja patril mezi ty stastnejsi.  
  
A jak to probihalo..  
Dostal jsem na papiru zadani:  
  
Napiste gramatiku pro jazyk {a^ib^jc^k, i>j>k}, dokazte, ze neni bezkontextovy. Definujte monotonni a kontextovou gramatiku, formulujte a dokazte vztah mezi nimi.  
  
Inu, gramatika vypadala nejak takto:  
  
S' -> AABS (pro slovo bez c)  
S -> ABSc | ABc (za kazde c musi prijit i a,b)  
B -> ABB (muzem mnozit B, ale pritom musime pridat A)  
A -> AA (A muzem mnozit jak chcem)  
  
BA -> AB (setrizeni; careful, toto neni kontextove pravidlo, ale jde predelat: BA->BX; BX->YX; YX->AX; AX->AB)  
  
Bc -> bc  
Bb -> bb  
Ab -> ab  
AA -> aa  
  
mozna tam najdete drobne chybky, kazdopadne takto nejak to vypadalo.  
  
Pak dukaz, ze jazyk neni kontextovy - pomoci pumpingu. Protoze jsem tam mel nejasnosti, nechal mi ho i formulovat, spolu jsme to zvladli :) a pak jsem uz korektne rozhodl, ze jazyk neni kontextovy.  
  
Co se monotonnich a kontextovych gramatik tyce, maji stejnou silu (malinko zlobi jen lambda). Kontextova je monotonni (az prave na lambdu), a to, ze monotonni lze prevest na kontextovou se dela pomoci separovanych gramatik. Je to uplne easy, akorat jen na 3 strankach ve slidech c. 10. Presto, s pouhou znalosti definic techto dvou gramatik jsem to z toho vykopal.  
  
Uplne se mu to nezdalo, tak resil, co jsem mel v testu spatne - prave prunik BKJ a RJ (ze je BKJ). Dal mi dost casu na to, abych dosel k tomu, ze jejich dva automaty (ZA a KA) jdou spojit.   
  
Pak se jeste ujistil, ze nejsem naprosty ychtyl, otazkou sila ZA prijimajicih stavem a prazdnym zasobnikem - jsou stejne silne, ptal se, jak prevest ZA-zasobnikem na ZA-stavem (prihodit novy symbol na spodek zasobniku, dva stavy a par instrukci..).  
  
Nakonec se rozhodl ze teda za jedna, kdyz jsem na vsechno dosel. Z toho jsem usoudil, ze je to fakt hodny typek a chtel mi pomoct... pozdeji jsem zjistil ze vyhodil aspon polovinu lidi.  
  
  
Inu, zaverem, bez znalosti definic a zneni vet to nema cenu. Je dobre umet definovat automat (vsechny typy), jazyk i gramatiku. S tim uz se da slusne operovat. Kazdopadne preju vsem hodne stesti, Bartak to nehroti, dal mi vzdycky cas na rozmyslenou, kdyz jsem placl nesmysl (a ze jich bylo), rekl, ze ne, ze to bude trosku jinak... Ale to mluvim za sebe, jini to asi vidi v jinem svetle.  
  
See ya :)
<{/ForumPost}>

<{ForumPost(poster="Jochanan", timestamp=2007-05-29 16:32:03)}>
Já měl jako zadání určit a dokázat, jakej je jazyk, který přijímá slova ve tvaru ww kde w =(0,1)*  
Je to kontextový (napsal jsem typu 0, protože jsem si tím nebyl jistej), pak jsem měl zformulovat a dokázat něco, abych dokázal, že to neni v nějaký podtřídě. Tedy pumping lemma pro bezkontextový jazyky. a nakonec to předvést na tom zadanym jazyku. To se mi podařilo zčásti, protože když si člověk uvědomí, tak to přijímá i slova že w = wR (reverse) a ty jsou bezkontextový, tak to nevim, jak to pak dokazovat...  
  
(jo, proč ten jazyk je kontextovej = protože stačí TS s páskou stejně dlouhej jakoto slovo. Najdeme prostredek (umíme), uděláme značku, a pak už to je easy...)  
  
Nakonec mi nabídnul trojku, radši jsem jí vzal, ale mrzí mě to. Doporučoval bych si projít ty otázky toho kvízu, protože může (výrazně) ovlivnit známku.  
  
Jinak další zadání tam bylo že byl zadanej regulární výraz a chtěl ho převést na automat + ještě něco, víc jsem toho nestačil přečíst...
<{/ForumPost}>