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