2022 AFJ Prednáška č. 2 - Delenia gramatík, konečné automaty

Zhrnutie prednášky

Prednáška rekapituluje pojem formálneho jazyka ako množiny reťazcov, ktorú možno popísať syntaxou pomocou formálnych gramatík s terminálnymi a neterminálnymi symbolmi, počiatočným neterminálom a odvodzovaním (derivácia). Na dvoch príkladoch, gramatike pre jazyk aⁿbⁿ a gramatike pre jazyk aⁿbⁿcⁿ, sa ukazuje, že tvar pravidiel ovplyvňuje, aké jazyky sa dajú generovať. Jazyk aⁿbⁿcⁿ nemožno popísať gramatikou s jediným neterminálom na ľavej strane pravidiel. Preto sa gramatiky historicky delia do štyroch skupín podľa tvaru pravidiel, čo má vplyv na ich praktickú použiteľnosť. Ako prvá je zavedená regulárna gramatika, ktorá pripúšťa pravidlá tvaru neterminál → reťazec terminálov alebo neterminál → neprázdny reťazec terminálov s jedným neterminálom na konci. Ďalšie typy gramatík a konečné automaty budú nasledovať.

• - Formálny jazyk je množina reťazcov; jeho syntax sa popisuje formálnou gramatikou.
• - Gramatika pozostáva z neterminálov, terminálov, pravidiel a počiatočného neterminálu; tvorba reťazcov sa nazýva derivácia.
• - Konečná množina pravidiel môže popisovať nekonečný jazyk, napríklad syntax jazyka C.
• - Jazyk aⁿbⁿcⁿ sa nedá generovať gramatikou s jediným neterminálom na ľavej strane pravidiel.
• - Gramatiky sa delia do štyroch skupín podľa tvaru pravidiel, čo ovplyvňuje ich praktickú použiteľnosť.
• - Regulárna gramatika má pravidlá A → w alebo A → wB, kde w je reťazec terminálov (v druhom prípade neprázdny).
• - Pravidlá s dvoma neterminálmi na pravej strane alebo s terminálom za neterminálom regulárna gramatika nepripúšťa.

Zhrnutie pripravené s pomocou AI z prepisu videa.