Quiz 8

(1p) Which of the following regular expressions over {0, 1} denote the empty language?

1. ∅101∅

2. ∅ + (∅ + ∅)^*

3. ∅ + (∅ + ∅)⁺

4. (∅1∅)⁺

5. (0 + 1)^*

(1p) Consider the following DFA:

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.

(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

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