Rozdíl mezi regulární a bezkontextovou gramatikou

Gramatika má pro lingvistiku i programování jiný význam než pro běžného uživatele. Zatímco my často myslíme na gramatiku jako soubor pravidel slušného vyjadřování, lingvisté a programátoři ji vnímají jako soubor pravidel, který dokáže vygenerovat všechny možné věty v daném přirozeném či umělém jazyce. Mezi logicky možnými typy gramatik patří regulární a bezkontextové gramatiky, které se liší povolenými pravidly i typy generovaných výrazů.

Původ

Tyto pojmy zavedl lingvista Noam Chomsky ve své práci z roku 1959 „On Certain Formal Properties of Grammars“. Identifikoval několik základních typů gramatik, lišících se komplexitou generovaných jazykových struktur. Regulární gramatiky jsou jednodušší a méně výkonné než bezkontextové.

Rozdíl v pravidlech

Bezkontextové gramatiky umožňují pravidla, která kombinují jednotlivá slova (terminály) a skupiny slov – fráze (neterminály). V takové gramatice mohou slova i fráze vznikat v libovolném pořadí a ve větě může být libovolný počet těchto komponent. Naopak regulární gramatiky dovolují pouze jednotlivá slova a maximálně jednu frázi v každé větě. Navíc se fráze v regulární gramatice musí nacházet vždy na stejném místě.

Struktury

Díky širšímu souboru pravidel mohou bezkontextové gramatiky vytvářet rozmanitější struktury. Například větu „dívka z města s finančními problémy“ lze analyzovat různými způsoby – „s finančními problémy“ může popisovat město i dívku. Regulární gramatika takové nuance nedokáže zachytit; generuje pouze jednoduché řetězce nezávislých slov a případně jednu větší frázi, např. „velmi, velmi chytrí lidé“.

Použití

Bezkontextové gramatiky jsou klíčové v oblasti zpracování přirozeného jazyka (NLP), protože dokážou modelovat rekurzivní struktury, které jsou charakteristické pro lidský jazyk. Regulární gramatiky, jako podmnožina bezkontextových, se také používají, ale jsou vhodné jen pro krátké a gramaticky jednoduché úseky textu, typické pro neformální dialog.