Quiz 8

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 regular expressions over {0, 1} denote the empty language?

   1. ∅101∅

   2. ∅ + (∅ + ∅)^*

   3. ∅ + (∅ + ∅)⁺

   4. (∅1∅)⁺

   5. (0 + 1)^*

2. (1p) Consider the following DFA:

   	0	1
   → 0	1	2
   1	2	1
   2	2	4
   3	3	5
   * 4	4	5
   * 5	5	4
   6	6	6

   Which of the following statements are correct?

   1. State 0 is distinguishable from state 1.

   2. State 2 is distinguishable from state 3.

   3. State 4 is distinguishable from state 5.

   4. State 6 is distinguishable from state 0.

   5. State 0 is equivalent to state 2.

   6. State 1 is equivalent to state 3.

   7. State 2 is equivalent to state 5.

   8. State 3 is equivalent to state 6.

3. (1p) If the DFA of the previous exercise is minimised, which of the following DFAs do we get (up to renaming of states)?

   1. 	0	1
      → A	B	B
      * B	B	B

   2. 	0	1
      → A	B	C
      B	C	B
      * C	C	C

   3. 	0	1
      → A	B	C
      B	C	B
      C	C	D
      * D	D	D

   4. 	0	1
      → A	B	C
      B	C	B
      C	C	D
      * D	D	D
      E	E	E

4. (2p) Consider the following DFAs:

   1. 	0	1
      → 0	1	2
      1	2	3
      2	1	3
      * 3	2	0

   2. 	0	1
      → 0	1	2
      1	2	3
      2	1	4
      * 3	2	0
      4	1	1

   3. 	0	1
      → 0	2	1
      1	2	3
      2	1	5
      3	2	2
      4	4	4
      * 5	1	0

   Which of the following statements are correct?

   1. DFA 1 and DFA 2 define the same language.

   2. DFA 2 and DFA 3 define the same language.

   3. DFA 1 and DFA 3 define the same language.