Give a counterexample to show that the following construction fails to prove Theorem 1.49, the closure of the class of regular languages under the star operation.7 Let N₁ = (Q₁,Σ, δ, q₁, F₁) recognize A₁. Construct N = (Q₁, Σ, δ₁, q₁, F₁) as follows. N is supposed to recognize A^*₁ .

a. The states of N are the states of N₁.

b. The start state of N is the same as the start state of N₁.

c. F = {q₁} [ F₁.

The accept states F are the old accept states plus its start state.

d. Define δ so that for any q ∈ Q₁ and any α ∈ Σ_ε,

Show this construction graphically, as in Figure 1.50.

Theorem 1.49

The class of regular languages is closed under the star operation.

Figure 1.50

Transcribed Image Text:

Sõi (4, a) 81 (4, a) U {q1} qe Fi and a = e. q ¢ F1 or a + e 8(q, a) = q E F1 and a = €.