Ekvivalence konečných automatů a regulárních gramatik

Regulární gramatiky popisují všechny regulární jazyky a v tomto smyslu (ve schopnosti popisu jazyka) jsou ekvivalentní s konečnými automaty a regulárními výrazy. Regulární gramatika ja buď pravá regulární (neterminály jsou vpravo) nebo levá regulární (neterminály jsou vlevo).

Regulární jazyk je formální jazyk (množina (i nekonečná) slov složených z omezené abecedy), který:

může být akceptován deterministickým/nedeterministickým konečným stavovým automatem

Příkladem neregulárního jazyka je anbn, kde n > 1 (alespoň jedno a následované stejným počtem b), gramatika pro palindromy apod. - lze určit na základě Nerodovy věty, která se užívá v důkazech, že nějaký jazyk není rozpoznatelný konečným automatem

Každý regulární jazyk je rozpoznatelný konečným automatem; každý jazyk rozpoznatelný konečným automatem je regulární.

Kleenova věta: Libovolný jazyk je regulární, právě když je rozpoznatelný konečným automatem. Přechodový graf je T nad S je konečný orientovaný graf, jehož každá hrana je pojmenována jistým slovem wÎS*. Alespoň jeden z uzlů grafu je počáteční a některé uzly jsou koncové. Ke každému přechodovému grafu T nad abecedou S existuje regulární výraz R nad S takový, že 

 a ke každému regulárnímu výrazu R nad S existuje konečný automat A takový, že 

Postup převodu gramatiky na konečný automat

Potřebujeme získat gramatiku typu 3 ve standardní formě. 

Regulární gramatika je ve standardní formě, jestliže obsahuje pouze pravidla tvaru X → aY a X → a , X → e kde X,Y jsou neterminály, a je právě jeden terminál, e je prázdný symbol. Toho dosáhneme takto:

Původní gramatika typu 3 (lineární): G = (N, T, S, P)

 Požadovaná regulární gramatika: G’ = (N’, T, S, P’)

Požadovaná gramatika G’ bude mít stejné terminální symboly a stejný počáteční stav.

Konstrukce přechodů P’:

do P’ zařadíme všechna pravidla z P ve tvaru X → aY a X → e

za každé pravidlo X → x1 x2 x3 Y zařadíme do P’ soustavu pravidel:

X → x1 X1

X1 → x2 X2

X2 → x3 Y

za každé pravidlo X → z1 z2, zařadíme do P’ soustavu:

X → z1 Z1

Z1 → z2 Z2

Z2 → e

Místo pravidel tvaru X → Y musíme zajistit to, aby z každého stavu X pro který máme X → Y, bylo možné odvodit všechny řetězce, které lze odvodit z Y.

N’ vznikne obohacením N o všechny nově vytvořené neterminální symboly

Zkonstruujeme automat z nově vytvořené gramatiky

stavy budou odpovídat neterminálním symbolům

vstupy budou odpovídat terminálním symbolům

přechodovou funkci zkonstruujeme na základě analogií

X → aY ↔ přechod ze stavu X do stavu Y při vstupu symbolu a

počáteční stav bude odpovídat počátečnímu symbolu

množinu koncových stavů určíme z pravidel X → e

Tímto jsme získali nedeterministický konečný automat, který lze převést na deterministický konečný automat.
