CS 384 - Theory of Computation

Professor Simonson

Assignment 3

Due:  Monday, April  11

1.  Construct pushdown automata (non-deterministic if you wish) to accept the following languages. Please comment and explain your machines.
  1. {1n0n | n > 0}
  2. {0n12n | n >= 0}
  3. {1n0n | n > 0} U {0n12n | n >= 0}
  4. (0+1)* - {ww | w in (0+1)*} (This is the complement of ww that we discussed in class).

2.  Construct Deterministic Pushdown Automata to accept the following languages.   Again include comments.
  1. {10n1n | n > 0} U {110n12n | n > 0}.
  2. Binary strings that contain an equal number of 0's and 1's.
  3. Binary strings with twice as many ones as zeros.
  4. Binary strings that start and end with the same symbol and have the same number of 0’s and 1’s.

3.  Construct Context Free Grammars to accept the following sets.  Explain your grammars.
  1. {0n1n | n > 0} U {0n12n | n > 0}
  2. Binary strings that start and end with the same symbol.
  3. Binary strings whose length is odd.
  4. Binary strings with odd length whose middle symbol is zero, 
  5. {0i1j2k | i != j or j != k}. 
  6. Binary strings with twice as many ones as zeros.

4.  Ambiguity in Grammars
a.  Prove that the grammar below that generates strings with an equal number of 0's and 1's is ambiguous. Explain.
S --> 0A | 1B
A --> 0AA | 1S | 1
B --> 1BB | 0S | 0

Extra Credit:  Construct an unambiguous grammar for this language.
b.  Consider this grammar that generates a natural fragment of a programming language, where the non-terminal symbols are upper case and enclosed in angle brackets; the terminal symbols are lower case
<STMT>     -->     <ASSIGN> | <IF-THEN> | <IF-THEN-ELSE> | <BEGIN-END>
<IF-THEN>               -->     if condition then <STMT>
<IF-THEN-ELSE>     -->     if condition then <STMT> else <STMT>
<BEGIN-END>   --> begin <STMT-LIST> end
<STMT-LIST>          -->   <STMT-LIST> <STMT> | <STMT>
<ASSIGN>    -->  a:=1
Prove that the grammar is ambiguous.

                Extra Credit:  Construct an unambiguous grammar for the same language.

5.  Chomsky Normal Form
  1. Put the following grammar into Chomsky Normal Form, where e is lambda.   Show all work.
S --> A | AB0  |  A1A
A --> A0 | 1  |  AC1AC
B --> B1  |  BD
C --> ABC  |  CAS  |  1CS   |  e
D -->  DB  | DD0D | 0 |  1
 
  1. Convert the following grammar to an equivalent one with no unit productions and no useless symbols. Show that the original grammar had NO useless symbols. What useless symbols are there after getting rid of unit productions? 

    2. S --> A | CB 
    C --> 0C | 0
A --> C | D
D --> 2D | 2
B --> 1B | 1
  1. Show that if G is a CFG in Chomsky Normal Form (CNF) then for any string w in the language generated by G, that has length n>=1, exactly 2n-1 steps are required for any derivation of w.
  1. Let G be a CFG in CNF with n non-terminal symbols. Show that if some string is generated with a derivation of more than 2n steps, then the language generated by G is infinite. (Note: this fact is used in the pumping lemma and in decision algorithms related to parsing.)

6. Parsing and the CYK Decision Algorithm

 a.   Exhibit the table you get by doing the CYK algorithm on the strings 00000 and 000000 for the grammar below.

S --> AB | BC  A --> BA | 0
B --> CC | 1  C --> AB | 0

 b.   Write a NPDA that accepts exactly what the grammar above generates.


7.  Two-Way PDA’s
A 2-way PDA is a machine that is just like a deterministic PDA except that it can move either left or right on seeing a particular symbol in a particular state. It accepts if it moves off the right end of the input in a Final State.
Show that the set {0n1n0n | n > 0} is accepted by a 2-way PDA.You may assume that there is a # symbol at the end of the string and a $ symbol at the beginning to mark the end points. To draw a 2-way PDA, just add R (right) or L (left) to each transition (so each arrow now will have an input symbol, a stack symbol, a push/pop command and an L or an R).
(Note that the set above is not accepted by any NPDA, so it is not a CFL).