1. a) G 1 is a context-free grammar with start symbol S 1 , and no other nonterm

Question

1. a)

G1 is a context-free grammar with start symbol S1, and no other nonterminals whose name begins with "S." Similarly, G2 is a context-free 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 concatenation 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)L(G2)?

a) S S1S3, S3 S2 |

b) S S1S3S2, S3

c) S S1S1, S1 S2

d) S S1.S2

-

1. b)

Let L be the language of the grammar:

The operation max(L) returns those strings in L that are not a proper prefix of any other string in L. Determine the language max(L) and identify in the list below the one string that is in max(L).

a) aabbbbcaa

b) abbca

c) abbcaa

d) aaaaabc

a) S S1S3, S3 S2 |

b) S S1S3S2, S3

c) S S1S1, S1 S2

d) S S1.S2

Explanation / Answer

1)a)

answer:D

explanation:

here we are concatenating languages of two grammers ,L(G1)L(G2)

means the strings of L(G1) comes first and then strings of L(G2)

s1 - will lead to generate strings of L(G1)

s2 - will lead to generate strings of L(G2)

so...the grammer would be

s->s1s2

1)b)

proper prefix: of a string is a prefix that is not a string itself

max(L): returns the string that is not a proper prefix, means returns the complete string belongs to L

so,from the below the string belongs to L ,that is returned max(L) is

answer: B

abbca

it can be generated from grammer

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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