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]
…
Pozn.: L(G) = {ambn : m, n ³ 1}
• S Þ aS
[1] Þ aaA
[2] Þ aab [4]
• S Þ aA
[2] Þ abA [3] Þ abb [4]