CS 301 - Languages and Automata

Professor Simonson

Assignment 3   (40 points)

Due:  Monday, April 7

1.  Construct pushdown automata (non-deterministic if you wish) to accept the following languages. Make sure to comment and explain your machines.  (5 points)
  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. (7 points)
  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.(Difficult)
  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.  (10 points)
  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
(4 points)
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 (8 points)
  1. Put the following grammar into Chomsky Normal Form.   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 (4 points)

 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 (2 points)
A 2-way PDA is a machine that is just like a deterministic PDA except that it can move either left or right on the input string after seeing a particular symbol in a particular state. It accepts if it moves off the right end of the input in a Final State.  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).
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. Explain your idea with comments.

Point of interest:  2-way PDAs do not fit in perfectly to our "Bullseye" hierarchy of Regular Sets, DCFLs, CFLs, and TM languages.  Cearly, the 2-way PDA languages are contained in TM languages and they contain the DCFLs, however,. the 2-way PDA languages neither contain nor are contained by CFLs.  The set {0n1n0n | n > 0}, for example, is accepted by a 2-way PDA but you can use the punping lemma to prove that it is not a CFL.  Also, the set {0n1n | n > 0} U {0n12n | n > 0} is a CFL but is not accepted by any 2-way PDA.  Finally, pallindromes are accepted by both machines, so they have some thing in common..