Regulární gramatika
Regulární gramatika je typ formální gramatiky. Přesněji je to gramatika typu 3 podle Chomského hierarchie, tedy ta nejzákladnější.
Regulární gramatika se formálně zapisuje, jako čtveřice , kde G značí regulární gramatiku, N je konečná neprázdná množina neterminálů, T je konečná neprázdná množina terminálů, P je konečná neprázdná množina nezkracujících pravidel a S je startovací neterminál z množiny N.
Regulární gramatika se využívá pro generování formálních jazyků, této vlastnosti se využívá především v oboru informatiky, pro teorii jazyků a překladačů, konečný automat založený na RG se využívá například v lexikální analýze překladače.
Gramatika typu 3 obsahuje pravidla tvaru a , kde X,Y jsou neterminály a je řetězcem terminálů. Gramatika také může obsahovat pravidlo v případě, že se nevyskytuje na pravé straně žádného pravidla.[zdroj?!] Rozšíření regulární gramatiky o řetězce vytvořené z terminálů na levé straně a neterminálů na pravé, se nazývá pravá regulární gramatika.
Obdobně se definují i levé regulární gramatiky, které obsahují pravidla tvaru a , kde X,Y jsou neterminály a w je řetězcem terminálů. Lze dokázat, že pravé a levé lineární gramatiky jsou ekvivalentní, například právě pomocí derivačních stromů.
Gramatika je ve standardní Chomského formě CNF (regulární formě), jestliže obsahuje pouze pravidla tvaru a , kde A,B a C jsou neterminály, a je právě jeden terminál.
Jazyky generované regulárními gramatikami, jsou nazývány regulární jazyky a jsou to takové jazyky, které přijímá konečným automatem.
To zda je gramatika opravdu regulární, nebo spíše, že není, se dá dokázat pomocí důkazu sporem za použití Pumping Lemma.
Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |
Teorie automatů: formální jazyky a formální gramatiky | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Každá úroveň jazyků je podmnožinou své nadřazené úrovně. – Každý automat a každá gramatika má svůj ekvivalent v nadřazené úrovni. |