S S / | \ / | \ S or S S and S / | \ | | / | \ S and S r p S or S | | | | p q q r
S -> T implies S | T T -> T or U | U U -> U and V | V V -> p | q | r | (S)
S S / \ / \ S S S S / \ /|\ /|\ / \ S S ( S ) ( S ) S S /|\ /|\ | | /|\ /|\ ( S )( S ) ( S )( S ) | | | |
S -> lambda | ( S ) S
We prove now G is not ambiguous. By structural induction: Consider a string x in L(G). We have two cases:
S // | \ ( S ) S | | ty tz
S -> a b b | a S b b
We prove now that L(G) = L where L = {a^{n}b^{2n} | n > 0}
S -> T U T -> lambda | a T b U -> lambda | b U c
We show now that L(G) = L, where L = {a^{k}b^{m}c^{n} | m = k + n}.
Let G_{1} be the subgrammar with productions
T -> lambda | a T band let G_{2} be the subgrammar with productions
U -> lambda | b U cClearly, L(G) = L(G_{1})L(G_{2}). In fact, x is in L(G) iff S -> T U ->^{*} x, but this is possible iff there exist y, z such that T ->^{*} y, U ->^{*} z, and x = y z.
Let L_{1} be the language {a^{k}b^{k} | k >= 0} , and let L_{2} be the language {b^{n}c^{n} | n >= 0}. We are going to show that L(G_{1}) = L_{1} and L(G_{2}) = L_{2}. Since L = L_{1}L_{2}, we can conclude that L(G) = L.