Quiz 5

The first four questions refer to the ε-NFA given by the following transition table:

1. (1p) Which states (if any) belong to the ε-closure of the set of states {q₁, q₃}?

   1. q₀

   2. q₁

   3. q₂

   4. q₃

   5. q₄

   6. q₅

   7. q₆

   8. q₇

2. (1p) If the ε-NFA is in state q₅ and the next input symbol is 0, what states (if any) is the ε-NFA in after processing this symbol (i.e., what is δ_hat(q₅, 0), where δ_hat is the extended transition function)?

   1. q₀

   2. q₁

   3. q₂

   4. q₃

   5. q₄

   6. q₅

   7. q₆

   8. q₇

3. (1p) If the ε-NFA is in state q₀, what states (if any) is the ε-NFA in after processing the string 011 (i.e., what is δ_hat(q₀, 011), where δ_hat is the extended transition function)?

   1. q₀

   2. q₁

   3. q₂

   4. q₃

   5. q₄

   6. q₅

   7. q₆

   8. q₇

4. (1p) Which of the following strings (if any) are in the language of the ε-NFA?

   1. ε

   2. 00

   3. 000001

   4. 0110

   5. 100001

5. (1p) Now consider the following ε-NFA:

   	ε	0	1
   → q₀	{q₁}	∅	∅
   q₁	∅	{q₂}	∅
   q₂	∅	∅	{q₃}
   q₃	{q₀, q₄}	∅	{q₃}
   * q₄	∅	∅	∅

   If the subset construction for ε-NFAs is applied to this ε-NFA and all inaccessible states are removed, which of the DFAs below is equal, up to renaming of states, to the DFA that is obtained?

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

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

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