Quiz 7

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) What ε-NFA is the result of using the construction from Theorem 3.7 in the main text book to convert the regular expression (ε + 10)^* into an ε-NFA over {0, 1}?

   1. 	ε	0	1
      → 0	{1}	∅	∅
      1	{2, 4}	∅	∅
      2	{3}	∅	∅
      3	{7}	∅	∅
      4	∅	∅	{5}
      5	∅	{6}	∅
      6	{7}	∅	∅
      7	{1, 8}	∅	∅
      * 8	∅	∅	∅

   2. 	ε	0	1
      → 0	{1, 8}	∅	∅
      1	{2, 4}	∅	∅
      2	{3}	∅	∅
      3	{7}	∅	∅
      4	∅	∅	{5}
      5	∅	{6}	∅
      6	{7}	∅	∅
      7	{1, 8}	∅	∅
      * 8	∅	∅	∅

   3. 	ε	0	1
      → 0	{1}	∅	∅
      1	{2, 4}	∅	∅
      2	{3}	∅	∅
      3	{8}	∅	∅
      4	∅	∅	{5}
      5	{6}	∅	∅
      6	∅	{7}	∅
      7	{8}	∅	∅
      8	{1, 9}	∅	∅
      * 9	∅	∅	∅

   4. 	ε	0	1
      → 0	{1, 9}	∅	∅
      1	{2, 4}	∅	∅
      2	{3}	∅	∅
      3	{8}	∅	∅
      4	∅	∅	{5}
      5	{6}	∅	∅
      6	∅	{7}	∅
      7	{8}	∅	∅
      8	{1, 9}	∅	∅
      * 9	∅	∅	∅

2. (1p) Which of the following regular expression equivalences are valid?

   1. L(M + N + M) = LN + LM

   2. MN = (N + ∅)(Mε)

   3. (∅M)^* = ((εε)^*)^*

   4. (M + N)^* = M^* + N^*

   5. M^* = ε + MM^*

3. (1p) Which of the following regular expression equivalences are valid?

   1. (ε + M)^* = M^*

   2. (MN)⁺ = M(NM)^*N

   3. (M + N)(M + N) = MM + MN + NN

4. (1p) Consider the language L over {0, 1} defined by the regular expression (01)^*. According to the pumping lemma for regular languages there is some m ∈ ℕ such that P(m) holds, where P(m) is the property ∀w ∈ L. |w| ≥ m ⇒ ∃t, u, v ∈ {0, 1}^*. w = tuv ∧ u ≠ ε ∧ |tu| ≤ m ∧ ∀n ∈ ℕ. tuⁿv ∈ L. What is the smallest m ∈ ℕ for which P(m) holds?

5. (1p) Which of the following languages are regular?

   1. {w ∈ {0, 1}^* | (|w| = 5 ∧ ∄u, v ∈ {0, 1}^*. w = u00v) ∨ |w| = 3}

   2. {(uv)² | u ∈ {0}⁺, v ∈ {1}⁺}

   3. {u²v² | u ∈ {0}⁺, v ∈ {1}⁺}

   4. {w² | w ∈ {0, 1}^*}