CIS 420/520 Assignment 3
Regular Expressions, Pumping Lemma
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 3 is due Wednesday, October 24
Sipser 1.21a
Use the procedure described in Lemma 1.60 to convert the following finite
automaton to a regular expression.
Sipser 1.46
Prove that the following languages are not regular. You may use the
pumping lemma and the closure of the class of regular languages under
union, intersection, and complement.
-
{ 0n1m0n | m,n ≥ 0 }
-
{ w | w ∈ {0,1}* is not a palindrome }
Sipser 1.53
Let Σ = { 0, 1, +, = } and
ADD = { x=y+z | x,y,z are binary integers
and x is the sum of y and z }
Show that ADD is not regular.
Sipser 1.48 (for CIS 520 students)
Let Σ = {0,1} and let
D = { w | w contains an equal number of occurrences of the substrings 01 and 10 }
Thus 101 ∈ D because 101 contains a single 01 and a single 10,
but 1010 ∉ D because 1010 contains two 10s and one 01. Show that
D is a regular language.