Regulární gramatika
![ikona](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Broom_icon.svg/48px-Broom_icon.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Preferences-system.svg/16px-Preferences-system.svg.png)
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. |