Deterministické a bezprefixové PDA
Osnova sekce
-
-
Studenti musíOznačit jako hotovo
9. video přednáška 2019
- 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.
-
Studenti musíOznačit jako hotovo
Test možná předbíhá cvičení; teď můžete tipovat, je to ukázka úloh, které vás mohou potkat v závěrečném testu.
-