# Finding a DFA with same language as given $\epsilon$-NFA

Consider the following automaton.

How does one find a DFA with an equivalent language using an algorithm? In particular, I was requested to use the algorithm described in the answer to this question. The problem arises from the fact that $$a, b$$ both map to $$q_{1}$$. Taken then the epsilon closure of $$q_{0}$$, denoted here $$[q_0$$]. It is $$[q_0] = \{q_{0}, q_{2}\}$$. But then one finds that

$$\delta([q_0], a) = \delta([q_0], b) = \{q_{0}, q_{1}, q_{2}\}$$

In other words, following the algorithm, when finding the correct transitions for $$[q_0]$$, one encounters that it transitions to the same state via two different inputs. Which contradicts the fact that the automaton we are building should be deterministic.

How can one go about finding the DFA for the NFA above? What am I missing?

• Why does it contradict the fact that the automaton is deterministic? A NFA that is not a DFA has at least one of 1) epsilon-transitions, 2) two (or more) transitions from the same state and the same symbol. The DFA you are looking for contains a single state $Q$ which corresponds to the set of states $\{q_0, q_1, q_2\}$ of the NFA. The transitions are $\delta(Q, a) = \delta(Q, b) = Q$. State $Q$ is both the initial state and an accepting state. Jul 21, 2023 at 22:51
• Deterministic means that the same input cannot lead to different states, not that different inputs cannot lead to the same state. Jul 21, 2023 at 22:54
• I've been stuck with this all day, my dear Lord, thank you both for clarifying this. I had the definition wrong it seems. Jul 22, 2023 at 0:25