2022 AFJ Cvičenie č. 1 - Gramatiky, derivácie reťazcov

Zhrnutie prednášky

Cvičenie opakuje základy formálnych gramatík z prednášky: gramatika je súbor terminálov, neterminálov a pravidiel, pričom derivácia nahrádza ľavé strany pravidiel pravými. Zavádza pojem vetná forma, teda ľubovoľný reťazec symbolov gramatiky odvoditeľný z počiatočného neterminálu. Ďalej definuje jazyk generovaný gramatikou L(G) ako množinu všetkých terminálnych reťazcov odvoditeľných z počiatočného neterminálu. Motivačne to ilustruje gramatika jazyka C, ktorá konečným počtom pravidiel popisuje nekonečne veľa syntakticky správnych programov. Lektor spomína aj pôvod teórie u Noama Chomskeho, ktorý formalizoval gramatiku prirodzených jazykov, a na záver začína príklad s gramatikou s neterminálmi S, A a terminálmi 0, 1.

• - Formálna gramatika pozostáva z terminálov, neterminálov, pravidiel a počiatočného neterminálu.
• - Derivácia znamená nahrádzanie ľavých strán pravidiel ich pravými stranami v reťazci.
• - Vetná forma je každý reťazec symbolov gramatiky odvoditeľný z počiatočného neterminálu.
• - Jazyk generovaný gramatikou L(G) je množina všetkých odvoditeľných terminálnych reťazcov.
• - Konečný počet pravidiel môže popísať nekonečný jazyk, napríklad syntax programov v jazyku C.
• - Počiatočný neterminál si volí návrhár gramatiky alebo ho určuje zadanie úlohy.
• - Teóriu gramatík v 50. rokoch založil Noam Chomsky pri snahe formalizovať prirodzený jazyk.

Zhrnutie pripravené s pomocou AI z prepisu videa.