CS 330 Homework 2 – FA and Regex

Give solutions to the problems listed below. Your automata diagram should be legible with clearly labeled paths and states. preferrable created by using software tools such FSMD by Evan Wallace. Use software to complete this HW, save as PDF, and submit on Moodle. by 10 PM Monday (2/5).

1. The following is a state diagram for a Finite Automata. Answer the following questions:

1. What is the start state and the set of accept states? (4)

1. Draw the computing tree for the string 011011. Is it accepted and why? (10)

1. For each of the following languages on alphabet ∑ = {0, 1}, give two strings that are member and two that are NOT. (8X2=16)

1. 0^*1⁺0^*

1. ∑^*00∑^*

1. Give regular expressions for each of the following languages where ∑={0, 1}. (3x10=30)

1. Words where every 1 is followed by one or more 0s.

1. Words that contain exactly two 0s and two 1s.

1. Words where the first digit is different from the last one.

1. Give FA (either DFA or NFA) on alphabet {0, 1} that represents/recognizes for the following languages. Do any 5 of the 6. (5X8 = 40 points)

1. The language containing words where every 1 is followed by one or more 0s.
2. The language containing words where the first digit is different from the last one.
3. The complement of A (i.e., the language described in A).
4. Reverse of A
5. Union of A and B
6. Intersect of A and B