I have these two deterministic context-free grammars:
G1 and G2
with G1=(N1,T,P1,S1) and G2=(N2,T,P2,S2)
(note that both grammars share the same set of terminal symbols)
I need to construct a grammar G3 with L(G3)=L(G1){L(G2)}*
I think the crucial point here is the common set of terminals. But I don't know how to proceed...
Any help?
The common set of terminals is not really crucial but makes things a bit easier. Let us suppose that N1 and N2 have no symbols in common and that S and X are not in either of the sets. Then the grammar:
[N1+N2+{S,X}, T, P1+P2+{S->S1X, X->S2X, X->lambda}, S]
generates the language you want.
The new rules generate some string from S1(S2)*. From there on you obviously can generate a word from L(G1) followed by any number of words from L(G2). The dijointness of nonterminal alphabets guarantees that the two grammars do not interfere with each other's parts of the derivation.
