Automata and Grammars

Marta Vomlelová

personal webpage

Book

The Automata and Grammars lecture follows the book J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computations, Addison–Wesley, aviable also as a pdf.

Slides

I put the key definitions and theorems on my slides. Check the first slide for the list of topics. The finite automata staff (slides 2-41) you refershed writing you homework. I intend to start my oral presentation at slide 42 (Chomsky Hierarchy) and continue with grammars, Pumping lemma and Turing machines.



Automaty a gramatiky

po dobu trvání distanční výuky je základem sledování záznamů přednášek
a pravidelná možnost online setkání na MS Teams v pondělky 10:40, tedy v době, kdy se měla konat přednáška.
Až na drobné úpravy přednášky sledují slajdy.

Na 23.3. připadá 6. přednáška, úvod do gramatik.

Na videu slajdy blikají, může sledovat na slajdech vedle, jen jsou číselně posunuté, 111-140, z zápatí vprostřed hlejte Gramatiky... 6.
Minuta 47: příklad na levou a pravou derivaci na tabuli není vidět: je to srozumitelné ze slajdu? Pokud ne, dejte vědět.
Minuta 1:12: Pokud budete moc přeskakovat, tak dole jsou identifikátory I, na nimy termy T.
Minuta 1:17: Skončit, už úvod pro další přednášku.

Na 30.3. připadá 7. přednáška, zásobníkové automaty.

V čase 18:42 Na tabuli chybně pravidlo. Pravidlo i,Z0 má připsat DVĚ Z a Z0, na tabuli připisuje jen jedno Z.
Na konci v čase 23:18 pak e vezme ze zásobníku Z a lambda krokem přejde do přijímajícího stavu.
A dvě 'je prvkem' na tabuli mají být opačným směrem.

Převod přijímání zásobníkovým automatem na generování gramatikou pokračuje ještě v 8.přednášce do minuty 31:00 . Je na Vašem zvážení, jestli shlédnete tento či příští týden.

Na 6.4. připadá 8. přednáška, Chomského normální forma a "Pumping (iterační) lemma pro bezkontextové jazyky".

Na konci 8. přednášky je "Pumping (iterační) lemma pro bezkontextové jazyky". Obě pumping lemmata a definice věcí v Chomského hierarchii považuji za nejdůležitější základ toho, co máte umět u zkoušky.
Pokud si nejste jisti, že stihnete shlédnout toto video do konce, přeskočte na minutu 31., do minuty 31 je převod zásobníkového automatu na gramatiku.

Naopak 9. přednáška začíná opakováním Pumping lemmatu a dalšími příklady. Můžete se podívat nebo použít na zopakování po velikonocích.

Řešení příkladu na konci přednášky není úplné. Rozdělení na vx nemůže obsahovat zároveň 0 a 2. Pokud obsahuje 0 nebo 2, poruší se rovnost počtu 0 a 2, jak je řešeno na přednášce.

Je třeba ještě zvážit variantu, že vx neobsahuje ani 0 ani 2. Protože je vx neprázdné, obsahuje 1 a pumpováním se poruší rovnost počtu 0 a 1.

13.4. je velikonoční pondělí, není výuka, užijte volna.

20.4. 9. přednáška

Prvních 15 min
'opakování' pumping lemmatu a jeho použití. Kdo si je jistý, že ho umí, může přeskočit. Kdo ne, je důležité umět či se hlásit cvičícímu nebo mě že mu není jasné.
0:15-0:35
CYK - algoritmus náležení slova do jazyka; tato 'snadná' otázka u obecných gramatik a Turingových stromů už snadná nebude.
0:35-0:43:28
Deterministické zásobníkové automaty
0:43:28- 0:54:40
přeskočte, rozšiřující a zamotala jsem se tam. Pro hloubavé: prostřední varianta je správně: bez lambda transakcí, hranu vedu do sourozence cíle plus y přepíšu na z; Pak výsledek odpovídá slajdu.
0:54:40-1:06
Vajíčko: naučte se nazpaměť; pokud možno i s důkazy, že jazyky do tříd patří a do menších nepatří.
1:06-1:10:43
(Ne)jednoznačnost gramatik - můžete vynechat
1:10:43
Uzávěrové vlastnosti (první půl): Bezkontextové jazyky nejsou uzavřené na průnik, jsou na sjednocení, konkatenaci, průnik s regulárním jazykem.
Pozn: 1:14:08 chybí pravá složená závorka na tabuli za {S->S1 S2
na slajdu 190 opraven regulární jazyk F na R.

23.4. 10. přednáška

Uzávěrové vlastnosti reguláních, bezkontextových a deterministických bezkontextových jazyků.
58:37: zůstanu s prázdým bufferem, nikoli zásobníkem
1:04 Pumpovatelný ne-bezkontextový jazyk

4.5. 11.přednáška

Je docela hutná. Nejdůležitější je znát všechny definice a věty (což není moc) a umět napsat Turingův stroj rozpoznávající daný jazyk.
Na slajdy jsem doplnila definici 'odvození v konečném počtu kroků', definovanou rekurzivně pro 0 a pro (n+1) kroků.

11.5. 12. přednáška

Kontextové a monotónní gramatiky a lineárně omezené automaty, diagonální a univerzální jazyk Důležité znát: definice, věty, umět napsat kontextovou/monotónní gramatiku k uvedeným a velmi podobným jazykům, případně popsat Turingův stroj dané jazyky přijímající (většinou mi stačí vámi vybraná metoda, zvlášť když znáte větu přijímá lin. omez. aut. právě když existuje kontextová gramatika.
Diagonální a univerzální jazyk.
Je toho hodně, jak jsem ostatně měla dojem v 1:08:17.

Opravy k řeči, slajdy jsou pokud vím dobře:
8:45
a^nb^nc^n není bezkontextový, je kontextový.
33:27
generuji monotónní gramatiku, kterou z předchozího umím přepsat na kontextovou
48:29
jsou rekruzivní, nejsou KONTEXTOVÉ, JSOU rekurzivně spočetné. Obrázek správně.
58:43
přijímá nulu, ne prázný řetězec (to by musel přijmout po přečtení blank, 000)
1:04-1:08:17
lze přeskočit, nevěřte mi že 1:08:17 přednáška končí.