Regulární gramatika

Tento článek potřebuje úpravy.

Můžete Wikipedii pomoci tím, že ho vylepšíte. Jak by měly články vypadat, popisují stránky Vzhled a styl, Encyklopedický styl a Odkazy.

---

Konkrétní problémy: článek vyžaduje zdroje a reference a úvodní vysvětlení

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 ${\displaystyle G=(N,T,P,S)}$, 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 ${\displaystyle X\rightarrow wY}$ a ${\displaystyle X\rightarrow w}$, kde X,Y jsou neterminály a ${\displaystyle w}$ je řetězcem terminálů. Gramatika také může obsahovat pravidlo ${\displaystyle S\rightarrow \epsilon }$ v případě, že se ${\displaystyle S}$ 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 ${\displaystyle X\rightarrow Yw}$ a ${\displaystyle X\rightarrow w}$, 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 ${\displaystyle A\rightarrow BC}$ a ${\displaystyle B\rightarrow 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.