1. a)

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

We wish to combine the symbols and productions of G₁ and G₂ to form a new grammar G, whose language is the concatenation of the languages of G₁ and G₂. The start symbol of G will be S. All productions and symbols of G₁ and G₂ 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(G₁)L(G₂)?

a) S S₁S₃, S₃ S₂ |

b) S S₁S₃S₂, S₃

c) S S₁S₁, S₁ S₂

d) S S₁.S₂

-

1. b)

Let L be the language of the grammar:

 S  AB A  aAb | aA |  B  bBa | c 

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