Pravé lineární gramatiky: Definice
Definice: Nechť G = (N, T, P, S) je BKG. G je pravá lineární gramatika (PLG), pokud každé pravidlo A ® x Î P splňuje: x Î T*  È T*N.
Myšlenka: BKG, ve které má každé pravidlo na pravé straně pouze řetězec terminálů následovaný max. jedním neterminálem
34/45
Příklad:
G = (N, T, P, S), kde N = {S, A}, T = {a, b}
P = {1: S ® aS, 2: S ® aA, 3: A ® bA, 4: A ® b }
• S Þ aA [2] Þ ab [4]
Textové pole: …
…
Pozn.: L(G) = {ambn : m, n ³ 1}
• S Þ aS [1] Þ aaA [2] Þ aab [4]
• S Þ aA [2] Þ abA [3] Þ abb [4]