Quiz 6

(1p) Which of the following strings, if any, are in the language of the regular expression 0^*11^*0?

1. 0101

2. 0110

3. 1001

4. 1010

(1p) Which of the following strings, if any, are in the language of the regular expression ∅ + 1 + ε?

1. ε

2. 0

3. 1

4. 00

5. 01

6. 10

7. 11

(1p) Which of the following regular expressions, if any, define languages that contain all of the strings 0101, 0110, 1001 and 1010?

1. (01)^*

2. (10)^*

3. (01)^* + (10)^*

4. (01 + 10)^*

(1p) Which of the following regular expressions, if any, define languages that are equal to L(A), where A is the following DFA over {0, 1}?

1. (01)^*

2. (1 + 01)^*

3. ((ε + 0)1)^*

4. 01(01)^*

5. 01(1 + 01)^*

6. 01((ε + 0)1)^*

7. 01(01)^*01

8. 01(1 + 01)^*(1 + 01)

9. 01((ε + 0)1)^*((ε + 0)1)

(1p) Which of the following regular expressions define languages that are equal to L(A), where A is the following DFA over {0, 1}?

Hint: The correct regular expression was constructed using (roughly) the method from Section 3.2.2 of the course text book, and then simplified a little. First state q₂ was removed, then q₄, then q₁, and finally q₃.

1. 0(1 + 10)1^*0(0 + 101^*0)^*

2. 0(0 + 10)1^*0(0 + 101^*0)^*

3. 0(1 + 10)1^*0(0 + 100^*0)^*

4. 0(0 + 10)1^*0(0 + 100^*0)^*