2022 AFJ Prednáška č. 4 - Regulárne výrazy, ich konverzia na NKA.

Zhrnutie prednášky

Prednáška sa začína oznámením prvého testu (20 bodov, 15 testových otázok so štyrmi možnosťami, v akademickom informačnom systéme), ktorý pokryje všetku látku od začiatku semestra vrátane regulárnych výrazov. Následne rekapituluje, že formálny jazyk je množina reťazcov a možno ho špecifikovať generatívne (gramatikou) alebo akceptačne (konečným automatom). Na príklade jazyka reťazcov z písmen a, b končiacich príponou ba ukazuje regulárnu gramatiku s tromi pravidlami aj nedeterministický konečný automat, ktorý ho akceptuje. Regulárna gramatika generuje regulárny jazyk. Niektoré jazyky, napríklad a^n b^n, však regulárnou gramatikou popísať nemožno, vyžadujú bezkontextovú gramatiku, čo vedie k Chomského hierarchii.

• - Prvý test je budúci týždeň o 9.00 v AIS, za 20 bodov, s približne 15 otázkami a jednou správnou odpoveďou zo štyroch.
• - Test pokryje látku od začiatku semestra vrátane dnešných regulárnych výrazov; potom pokračuje prednáška.
• - Formálny jazyk je množina reťazcov, ktorú možno popísať generatívne (gramatika) alebo akceptačne (automat).
• - Regulárna gramatika má pravidlá tvaru A → w alebo A → wB, kde w je neprázdna postupnosť terminálov, a generuje regulárny jazyk.
• - Jazyk reťazcov z a, b končiacich na ba popisuje regulárna gramatika aj nedeterministický konečný automat, ktorý sa dá determinizovať.
• - Jazyk a^n b^n nie je regulárny a regulárna gramatika ho nevie popísať; zvláda ho bezkontextová gramatika.
• - Chomského hierarchia zoraďuje gramatiky do tried podľa tvaru pravidiel a vyjadrovacej sily.

Zhrnutie pripravené s pomocou AI z prepisu videa.