CS154 Assignment #4

Due Monday, February 14, 2000, 3:15PM

1. (50 pts.) Here is an ambiguous CFG:

        S -> 0S | 1S | S0 | epsilon
   

   (The epsilon is intended to represent the empty string, not a sequence of 7 characters).

   (a)

   Describe informally the language of this grammar.

   (b)

   Give an example of a terminal string that has two leftmost derivations. Show those leftmost derivations.

   (c)

   Convert this grammar to a PDA that accepts by empty stack. You may either specify the PDA formally, as a 7-tuple with delta given by a list of rules, or as a transition diagram. In that latter case, we'll assume Z_0 is the start symbol.

   (d)

   Modify your answer to (c) so acceptance is by final state.

   (e)

   Give an unambiguous grammar for the same language.

2. (25 pts.)

   (a)

   Design a PDA that accepts the set of strings of 0's and 1's that have an equal number of 0's and 1's (in any order, e.g., 1001, epsilon, or 011011100010). Your PDA should accept by empty stack, and we suggest that it is important for part (b) that it has only one state.

   (b)

   Convert your PDA from (a) to a CFG that defines the same language.

3. (25 pts.) Here is a grammar; it generates the language with blocks of 0's followed by blocks of at least as many 1's, like the grammar we used in the class notes.

        S -> AAS | A | epsilon
        A -> 0A1 | 0B1
        B -> B1 | epsilon
   

   Convert the grammar to Chomsky normal form. Show the grammars that result from the intermediate steps --- elimination of useless symbols, elimination of epsilon-productions, elimination of unit productions. Note that the resulting grammar will not generate the empty string as the original grammar does.