Let M1 = (Q1, {q1}, ∆1, F1), where ∆1 ⊆ Q1 × (Σ ∪ {ϵ}) × Q1, be a non-deterministic finite automaton (NFA) accepting a language L1 ⊆ {0, 1} ∗ . Let ϵ denote the null string. We construct a new NFA M2 = (Q2, {q2}, ∆2, F2), where ∆2 ⊆ Q2 × (Σ ∪ {ϵ}) × Q2, as follows. • Q2 = Q1. • q2 = q1. • F2 = F1 ∪ {q1}. • (p, a, p′ ) ∈ ∆2 iff either (p, a, p′ ) ∈ ∆1 or (p ∈ F1 and a = ϵ and p ′ = q1) Prove or disprove: The language L2 accepted by M2 is L ∗ 1 .
