Formální jazyky a překladače: Proudění k přípravě na zkoušku

Proudění k přípravě na zkoušku. Bezkontextová gramatika. Derivační krok. Jazyk generovaný bezkontextovou gramatikou. Konstrukce bezkontextových gramatik. Zásobníkový automat. Konfigurace zásobníkového automatu. Přechodová relace. Jazyk přijímaný zásobníkovým automatem. Konstrukce zásobníkového automatu. Deterministický zásobníkový automat. Konstrukce deterministického zásobníkového automatu. Rozšířený zásobníkový automat. Analýza shora dolů. Analýza zdola nahoru. Úvod k LL-analýze. Množina Empty. Množina First. Množina Follow. Množina Predict. Konstrukce LL-tabulky. Poznámka k rekurzivnímu sestupu. Prediktivní syntaktická analýza. Nejednoznačnost bezkontextových gramatik, derivační strom. Úvod k precedenční syntaktické analýze. Konstrukce precedenční tabulky. Precedenční syntaktická analýza. Chomského hierarchie jazyků. Pumping lemma pro regulární jazyky. Komplementace konečných automatů. Chomského normální forma bezkontextových gramatik. Konstrukce bezkontextové gramatiky v Chomského normální formě. Rozhodnutelné problémy regulárních a bezkontextových jazyků. Uzávěrové vlastnosti regulárních a bezkontextových jazyků.

0:00:00 - Předehra
0:00:18 - Úvod
0:01:24 - Bezkontextová gramatika
0:08:55 - Derivační krok
0:21:05 - Jazyk generovaný bezkontextovou gramatikou
0:23:55 - Konstrukce bezkontextových gramatik
0:45:16 - Zásobníkový automat
0:52:54 - Konfigurace zásobníkového automatu
0:55:34 - Přechodová relace
1:01:27 - Jazyk přijímaný zásobníkovým automatem
1:07:00 - Konstrukce zásobníkového automatu
1:20:18 - Deterministický zásobníkový automat
1:25:13 - Konstrukce deterministického zásobníkového automatu
1:34:53 - Rozšířený zásobníkový automat
1:36:22 - Analýza shora dolů
1:51:38 - Analýza zdola nahoru
2:08:41 - Úvod k LL-analýze
2:12:10 - Množina Empty
2:19:30 - Množina First
2:33:13 - Množina Follow
2:50:03 - Množina Predict
3:00:35 - Konstrukce LL-tabulky
3:17:23 - Poznámka k rekurzivnímu sestupu
3:18:36 - Prediktivní syntaktická analýza
3:33:32 - Nejednoznačnost bezkontextových gramatik, derivační strom
3:43:40 - Úvod k precedenční syntaktické analýze
3:53:03 - Konstrukce precedenční tabulky
4:09:17 - Precedenční syntaktická analýza
4:28:52 - Chomského hierarchie jazyků
4:38:29 - Pumping lemma pro regulární jazyky
4:55:30 - Komplementace konečných automatů
5:03:39 - Chomského normální forma bezkontextových gramatik
5:14:34 - Konstrukce bezkontextové gramatiky v Chomského normální formě
5:20:31 - Rozhodnutelné problémy regulárních a bezkontextových jazyků
5:29:54 - Uzávěrové vlastnosti regulárních a bezkontextových jazyků
5:36:33 - Závěr
5:37:12 - Dohra