computer science assignment

Sample problem set 2

(Due before class on March 31st)
Problem 1. (Closure property of regular language) Construct DFAs for the following regular expression 
Problem 2. (Pumping lemma for regular languages) Show that the language is not regular a)
Problem 3. (Pumping lemma for CFL) Show that the following languages are not CFL a)
Problem 4. (Derivations, parse tree of CFL) Let CFG be
S à aSb | bY | Ya; Y à bY | aY | e

   1. Give a simple description of the CFL in plain English?
   2. Give leftmost and right most derivations of abbbb and bababa; and show the respective parse tree
   3. Is this language ambiguous?
   4. Construct a PDA for this CFL


Problem 5. (CFL) Show that C = {x#y | x, y Î {0,1}* and x ¹ y} is CFL
Problem 6. (Design of PDA) Design a PDA to accept the set of strings with twice as many 0’s as 1’s
Problem 7. (Language of PDA) Draw the diagram of the following PDA, which accepts on an empty stack.
P = ({p, q}, {0,1}, {Z, X}, d, p, Z, Æ) where the move function d is given by d(p, 1, Z) = {(p, XZ)}, d(p, e ,Z) = {(p, e)}, d(p, 1, X) = {(p, XX)}, d(q, 1, X) = {(q, e)}, d(p, 0, X) = {(q, X)}, d(q, 0, Z) = {(p, Z)}. Given some example strings in L(P).
Problem 8. (Chomsky normal form)
Begin with the grammar on {0, 1}:
S à ASB | e
A à aAS | a
B à SbS | A |bb

   1. Eliminate the e-production
   2. Eliminate any unit productions in the resulting grammar
   3. Eliminate any useless symbols in the resulting grammar
   4. Put the grammar into Chomsky Normal Form