Definice: Neomezená
gramatika (NG) je čtveřice G = (N, T, P, S), kde
• N je abeceda neterminálů
• T je abeceda terminálů, přičemž N Ç T = Æ
• P je konečná
množina pravidel tvaru
x ®
y,
kde x Î (N È T)* N(N È T)*,
y
Î
(N
È T)*
• S Î N je počáteční neterminál
• Čistě matematicky, P
je relace z (N
È T)*N
(N È T)* do (N È T)*
• Místo relačního zápisu
(x, y) Î P zapisujeme
pravidla x ® y Î P