The following lemma is from the book *Discrete groups* by Ohshika.



> 
> If a language $L$ is accepted by a non-deterministic automaton, then $L$ is regular, i.e., there exists a finite state automaton $M$ such that $L = L(M)$.
> 
> 
> 


Proof. Let $M = (\Sigma,A,\mu,F,\Sigma\_0)$ be a non-deterministic automaton accepting $L$. For a subset $X$ of the state set $\Sigma$, we define its $\epsilon$-closure, denoted by $\overline{X}$, to be the set of states that can be reached from $X$ by tracking arrows labelled with $\epsilon$ in finite steps. (The states in $X$ are regarded as being reached in $0$ steps, hence contained in $\overline{X}$.) We say that a subset $X$ such that $\overline{X} = X$ is $\epsilon$-closed.  

Let $Y$ be the set of $\epsilon$-closed subsets of $\Sigma$, where we regard the empty set also as being $\epsilon$-closed. We shall construct a finite state automaton whose state set is $Y$ as follows. For $a\in A$ and $X\in Y$, we define $Xa$ to be the $\epsilon$-closure of $\{s\in\Sigma\mid\text{ there exists }x\in X\text{ such that }(x,a,s)\in\mu\}$. We let the initial state be the $\epsilon$-closure of $\Sigma\_0$, and the final states the $\epsilon$-closed subsets containing at least one final state.  

It's easy to see that such a finite state automaton accepts the same languages $L$ as the non-deterministic automaton $M$. $\square$


The problem with the proof is that the resulting automaton is not a finite state automaton. (The initial state is not a single string) I'm a bit worried because this fact is used quite frequently in the later part of the book. Is this statement true? If so, where can I find the reference?


$\bullet$ I'll add definitions if someone requires in the comment.



If a language $L$ is accepted by a non-deterministic automation, then $L$ is regular
[Wikipedia](https://en.wikipedia.org/wiki/Powerset_construction) and [Hopcroft and Ullman](https://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation) require a unique start state for their NFA's. You can transform an NFA with many start states into an NFA with just one by adding a new state $q\_0$ and connecting it to all $q$ in $\Sigma\_0$ by $\epsilon$-edges.


It looks like Ohshika is following [Word processing in groups](https://en.wikipedia.org/wiki/Word_Processing_in_Groups), which allows many start states (see Definition 1.2.4). He is also following their proof (see Theorem 1.2.7). Unfortunately, there appears to be a small typo/mistake in WPIGs on line -8 of page 14 - at that location in the proof they seem to think that NFAs have a single start state.


In any case, in their construction (and in Ohshika's) the start state for the new DFA "should be" the $\epsilon$-closure of the set of start states of the original NFA.


