2022 AFJ Prednáška č. 3 - Nedeterministické KA, determinizácia

Zhrnutie prednášky

Prednáška sa začína organizačnými oznamami: 21. marca sa bude písať prvý test za 20 bodov v AIS počas prednášky, so 4 možnosťami odpovede a jednou správnou. Test pokryje formálne gramatiky, deterministické a nedeterministické konečné automaty a regulárne výrazy. Hlavná časť pripomína deterministický konečný automat a jeho prechodovú funkciu δ: Q × Σ → Q, ktorá pre každú dvojicu stav a vstupný symbol určuje najviac jeden nasledujúci stav. Takéto automaty, vrátane neúplných, ktoré sa pri nedefinovanom prechode zasekne, majú lineárnu zložitosť výpočtu vzhľadom na dĺžku vstupu. Nasleduje úvod do nedeterministických automatov, v ktorých môže byť z jedného stavu na ten istý symbol definovaných viac možných prechodov.

• - Test 21. marca o 9:00 v AIS, za 20 bodov, otázky s jednou správnou odpoveďou zo štyroch.
• - Test pokryje gramatiky, deterministické a nedeterministické KA a regulárne výrazy.
• - Typické otázky: ktorý reťazec automat akceptuje alebo gramatika generuje, a teoretické tvrdenia o vzťahoch gramatík.
• - Deterministický KA má prechodovú funkciu δ: Q × Σ → Q, ktorá dáva najviac jeden nasledujúci stav.
• - Neúplný DKA sa pri nedefinovanom prechode zasekne, čo je stále deterministické správanie.
• - Výpočet DKA má lineárnu zložitosť vzhľadom na dĺžku vstupného reťazca.
• - Nedeterministický KA môže mať z jedného stavu na ten istý symbol viacero možných nasledovníkov.

Zhrnutie pripravené s pomocou AI z prepisu videa.