Comp 330 (Fall 2024): Assignment 1

1. (10 points) Let Σ = {0, 1}. Draw a deterministic finite automaton (DFA) that accepts the language

L1 = {w|w has an even number of letters, and

                                w does not have two identical consecutive letters}

Hint: You can build a automaton for each language (i.e., “even number of letter” and “no two identical consecutive letters) then construct the product of the two’s.

2. (a) (10 points) Convert the following nondeterministic finite automaton (NFA) into a DFA.

(b) (5 points) Use your solution to build another DFA that accepts the complementary language L = { w | w L }

3. Write a regular expression describing the set of strings over the alphabet Σ = {0, 1} that:

(a) (10 points) Does not contain the string 110.

(b) (10 points) Start and end with the same letter.

4. Let Σ = {0, 1}. Show that:

(a) (10 points) the language L2 = { 0 k s0 k | k ≥ 1 and s ∈ Σ* } is regular.

(b) (10 points) the language L3 = { 0 k1s0 k | k ≥ 1 and s ∈ Σ* } is not regular.

5. We introduce the rotation operation on languages rot(L) = {xy | yx ∈ L }.

(a) (10 points) Show that rot(L) = rot(rot(L))). Start to show that rot(L) ⊆ rot(rot(L)). Then, show rot(L) ⊇ rot(rot(L)).

(b) (15 points) Show that a regular language L is closed under the operation rot(). Let ML be a DFA that recognizes L. Show how to build a NFA NL that recognizes rot(L).

6. (10 points) Using the k-path induction method, write a regular expression representing the language accepted by the following DFA. Show your work. Simplify the regular expression as much as you can.