Homework #4: Grammars CS 435 For questions 1, 2, and 3 use the following 10 grammars. Uppercase (lowercase) letters stand for nonterminals (terminals) and S is the start symbol in each grammar. G1 : S → aSb | ab G2 : S → bDc | Db | b D → bbDc | b | ϵ G3 : S → Sc | abS abSc → abbAcc bA → b G4 : S → Sc | Ec E → ab | aEb G5 : S → aU | bV U → bS | b V → aS | a G6 : S → cE | cS | dS | b cE → cdS | cd G7 : G9 : S AB A B → → → → AB BA a b S → bS | cS | bbS | ϵ G8 : G10 : S abbS aA A → → → → bS | aS abbb | abbaAA ab a S → bbSc | H H → cHdd | cd 1. For each of the 10 grammars listed above, indicate the smallest (most restrictions on production rules) class of grammars for which it belongs. Some of these grammars may generate languages that can be generated by a grammar with productions of a more restrictive form. Give answers based upon only the form of production rules in each grammar above. Indicate: Phrase-structured Grammar, ContextSensitive Grammar, Context-Free Grammar (with ϵ-productions allowed), or Regular Grammar (with ϵ-productions allowed). 2. Use exponential notation of symbols, where appropriate, and indicate explicit constraints on the exponents, when describing the following language sets. Also, you may enumerate the sentences in finite languages. Also, use the Kleene closure operator and set operators if necessary to completely describe the languages. Give a brief description of how you arrived at your answer. Formally describe each of the generated languages: 1 (a) L(G1) (b) L(G4) (c) L(G7) (d) L(G9) 3. Answer the following. (a) Show that G9 has at least one sentence in L(G9) that has two distinct rightmost derivations. (b) Does this prove that G9 is an ambiguous grammar? (c) How can one demonstrate that the language L = L(G9) is not inherently ambiguous? 4. Construct a context-free grammar Gwhiz that generates the language L(Gwhiz ) ⊆ {a, b, c}∗ = VT∗ : L(Gwhiz ) = {an b2n cm | n > 0, m > 0} 5. Construct a grammar that generates the language of non-negative even integers with no leading zeroes. So VT = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Some examples of sentences in the language: 0, 2, 10, 100, 10002, 1035798 . . .. Some examples of non-sentences (strings that are not in the language): 00, 02, 002, 7, 007, 123, . . .. For full credit construct a rightregular grammar.
