Right-Linear
Grammar: Definition
Definition:
Let G = (N, T, P, S) be a CFG. G is a right-linear grammar (RLG) if every rule A ® x Î P satisfies x Î T* È T*N.
A CFG in which every rule has a string of terminals followed by no more that one nonterminal on the right-hand side.
Gist:
34/45
Example:
G = (N, T, P, S), where N = {S, A}, T = {a, b}
P = {1: S ® aS, 2: S ® aA, 3: A ® bA, 4: A ® b }
• S Þ aA
[2] Þ ab [4]
…
Note: L(G) = {ambn : m, n ³ 1}
• S Þ aS
[1] Þ aaA
[2] Þ aab [4]
• S Þ aA
[2] Þ abA [3] Þ abb [4]