CIS 420/520 Home Page Last updated 2007/07/10 21:09:25

CIS 420/520 Assignment 1

Deterministic Finite Automata
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 1 is due Friday, October 5

Sipser 1.6

Give state diagrams of DFAs recognizing the following languages. In all parts the alphabet is {0, 1}.
  1. {w | w begins with a 1 and ends with a 0}
  2. {w | w contains at least three 1's}
  3. {w | w contains the substring 0101, i.e., w=x0101y for some x and y}
  4. {w | w has length at least 3 and its third symbol is a 0}

Sipser 1.36

Let Bn = { ak | where k is a multiple of n}. Show that for each n ≥ 1, the language Bn is regular.

Sipser 1.33 (for CIS 520 students)

Let
Σ2 = { [00], [10], [01], [11]}.
Here, Σ2 contains all colums of 0's and 1's of height two. A string of symbols in Σ2 gives two rows of 0's and 1's. Consider each row to be a binary number and let
C = {w ∈ Σ2* | the bottom row of w is three times the top row}.
For example, [00] [10] [11] [00] ∈ C, but [10] [10] [01] ∉ C.
Show that C is regular.
(You may assume the result claimed in Problem 1.31 - that the reverse of a language is regular.)