CODEWITHSUNDEEP
theoryformal-languages
de_dust
de_dust

Reputation: 291

How do I construct a formal grammar like that?

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?

Upvotes: 1

Views: 114

Answers (1)

Peter Leupold
Peter Leupold

Reputation: 1212

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.

Upvotes: 1

Related Questions