Quiz 6

If you cannot access Canvas and submit your answers via email, please only give the answers (a number or a list of numbers), and no motivating arguments.

1. (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

2. (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

3. (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)^*

4. (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}?

   	0	1
   → q₀	q₁	q₂
   q₁	q₂	q₃
   q₂	q₂	q₂
   * q₃	q₁	q₃

   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)

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

   	0	1
   → q₀	q₁	q₂
   q₁	q₃	q₄
   q₂	q₂	q₂
   q₃	q₅	q₃
   q₄	q₃	q₂
   * q₅	q₅	q₄

   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)^*