Quiz 7

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

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

(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

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

(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}^*}