CIS 420/520 Assignment 5
Push Down Automata, Non CFLs
The problems here are all from the second edition of the Sipser book. If you
are using the first edition, many of the problems are the same, but the numbering
of the problems is not.
Assignments are due at the beginning of class on the due date indicated.
Use machine copy if at all possible - in any case, writing and diagrams
must be neat and legible.
Assignment 5 is due Wednesday, November 14.
Sipser 2.13
Let G = (V,Σ,R,S) be the following grammar. V={S,T,U};
Σ={0,#}; and R is the set of rules:
S → TT | U
T → 0T | T0 | #
U → 0U00 | #
-
Describe L(G) in English.
-
Prove that L(G) is not regular.
Sipser 2.17
Use the results of Problem 2.16 (class of context free languages is closed
under the regular operations) to give another proof that every regular
language is context free, by showing how to convert a regular expression
directly to an equivalent context-free grammar.
Sipser 2.30d
Use the pumping lemma to show that the following language is not context free.
-
{ t1#t2#...tk | k≥2,
each ti ∈ {a,b}* and ti=tj for some i≠j }
Sipser 2.22
Let C = { x#y | x,y∈{0,1}* and x≠y }.
Show that C is a context free language.
Sipser 2.23 (for CIS 520 students)
Let C = { xy | x,y∈{0,1}*, |x|=|y| and x≠y }.
Show that C is a context free language.