CS 154 Introduction to Automata and Complexity Theory Handout 7

Winter 1996  R. van Glabbeek  January 31, 1996

Problem Set 4 Date Due: February 7, 1996

Reading: Floyd and Beigel, Chapter 0-5 to be read by Wednesday February 7’th.

Homework: Do the following exercises (FB refers to Floyd and Beigel The Language of Machines). Each problem must be submitted on a separate sheet. The homeworks must be solved without any collaboration.

Office hours change Popular demand has prompted Nikolaj to move his office hours to Tuesday and Thursday 4-5 in Gates 193. Thus, the new office hours are one hour later than previously.

Remember: The midterm is Friday February 16’th at the Annenberg Auditorium in the Cummings Art Building. It will cover Chapters 1-6.

1. (15 points) Consider the following regular language L: (a ∪ b)^{∗}a(a ∪ b) ∪ bb.

(a) Construct an NFA for L.

(b) Determinize the NFA into a DFA.

(c) Complement the DFA.

(d) Extract a regular expression for the complemented DFA.

2. (15 points) Solve problem 4.7-15

3. (15 points) State whether the following languages are regular and prove your answer:

(a) Given a fixed, arbitrary v ∈ (a ∪ b)^{∗}, let L_{v} = {wvw^{R} : w ∈ (a ∪ b)^{∗}, |w| > 0}.

(b) {wvw^{R} : w, v ∈ (a ∪ b)^{∗}, |w| > 0}

(c) {w : the number of occurrences of 01 as a substring of w equals the number of occurrences of 10 as a substring of w}

Extra credit problem (optional) One-dimensional checkers (due to Reynolds, appears in Manna, “Mathematical Theory of Computation”). Consider a one-dimensional (infinite) checkerboard where each square contains the letter a or b, for example,

⋯ a a b a a b b b a a b a a a a ⋯

There is always some word, starting and ending with b (baabbbaab in the example above) with an infinite string of a’s in both directions. A move in the game consists of jumping a b over a neighbor b to an a square as follows:

\underline{Before move} \underline{After move}

b b a^{⟶} a a b

or  a b b^{⟵}  b a a

Thus, when a b jumps it leaves a trail of two a’s in the direction of the jump. An initial board consists of a finite word w (starting and ending with b). w is said to be a winning word if there is a finite sequence of moves that will lead to a final board consisting of one b (and the rest a’s).

1. Express the set of all winning words as a regular expression over {a, b}.

Hint: Consider the final board and play backwards.

2. Prove your result.