19. Consider the following modification of Definition 2.6. An nfa with multipleinitial states is defined by the quintupleM = (Q, Σ, δ, Q0, F ) ,58 Chapter 2 Finite Automatawhere Q0 ⊆ Q is a set of possible initial states. The language accepted bysuch an automaton is defined asL (M ) = {w : δ∗ (q0, w) contains qf , for any q0 ∈ Q0, qf ∈ F } .Show that for every nfa with multiple initial states there exists an nfa with asingle initial state that accepts the same language.20. Suppose that in Exercise 19 we made the restriction Q0 ∩ F = . Would thisaffect the conclusion?

19. To show that for every NFA with multiple initial states there exists an NFA with a single initial state that accepts the same language, we can construct a new NFA as follows:

Let's denote the original NFA as M = (Q, Σ, δ, Q0, F) and the new NFA as M' = (Q', Σ, δ', q0', F').

1. Set Q' = Q ∪ {q0'}, where q0' is a new state not in Q.
2. Set Σ' = Σ.
3. Define the transition function δ' as follows: for each state q in Q and each symbol a in Σ, δ'(q, a) = δ(q, a). Additionally, for each state q0 in Q0, δ'(q0', ε) = q0. Here, ε represents the empty string.
4. Set q0' as the initial state of M'.
5. Set F' = F.

The new NFA M' has a single initial state q0' and accepts the same language as M. This is because from the initial state q0', M' can transition to any of the initial states of M without consuming any input (using ε-transitions), and from there the behavior of M' is identical to the behavior of M.

20. If we made the restriction Q0 ∩ F = ∅, it would not affect the conclusion. The construction of M' does not require any state to be both an initial state and a final state. The set of final states F' in M' is identical to the set of final states F in M, and the new initial state q0' is not a final state. Therefore, the language accepted by M' is still the same as the language accepted by M.