G1 is a context-free grammar with start symbol S1, and no other nonterminals who

Question

G1 is a context-free grammar with start symbol S1, and no other nonterminals whose name begins with "S." Similarly, G2 is a contextfree grammar with start symbol S2, and no other nonterminals whose name begins with "S." S1 and S2 appear on the right side of no productions. Also, no nonterminal appears in both G1 and G2.

We wish to combine the symbols and productions of G1 and G2 to form a new grammar G, whose language is the union of the languages of G1 and G2. The start symbol of G will be S. All productions and symbols of G1 and G2 will be symbols and productions of G. Which of the following sets of productions, added to those of G, is guaranteed to make L(G) be L(G1) [union] L(G2)?

a) S S1 | S3, S3 S2

b) S S1S2, S1 , S2

c) S S1S3, S3 S2

d) S S1, S1 S2, S2

Would you plz explain me? will learn for my knowldge

Explanation / Answer

--> Union of two languages is union of sets of strings of those two languages.
- i.e when we say we want to find union of two languages, we are actually finding union of set of strings of those two languages.

- Now, we have grammar G1 and G2 which generates two languages.
- We want to find Union of these two languages.
- Union of languages is Lang(G) with grammar G.
- For Any string x, x belongs to language Lang(G) if x belongs to Lang(G1) or Lang(G2).
- hence if a string is accepted by grammar G1 or grammar G2 then x is also accepted by Grammar G.
- hence correct answer is A) s->s1|s3, s3->s2
here A is equivalent to s->s1|s2.
which denoted that for any string x, if x is generated from s1 or s2 then it is generated from s.
where s is a starting symbol of grammar G.

if you have any doubts then you can ask in comment section.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.