Popis jak slova určitého jazyka generovat
Definice: (Formální gramatika)
je usp čtverce G = (V,T,S,P), kde:
-
V je neprázdná množina neterminálů
-
T je neprázdná množina terminálů
-
S náleží V je počáteční symbol
-
P konečná množina pravidel alfa → omega (řetězec alfa se přepíše na řetězec omega), přičemž alfa obsahuje alespoň jeden neterminál
Regulární gramatika
Definice gramatiku G= (V,T,S,P) nazveme regulární, pokud všechna pravidla jsou ve tvaru:
-
A → omega
-
A → omega B
kde A, B náleží V, ´omega náleží T*