Consider the following automaton.

enter image description here

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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Jul 21, 2023 at 22:51
  • $\begingroup$ Deterministic means that the same input cannot lead to different states, not that different inputs cannot lead to the same state. $\endgroup$
    – Nathaniel
    Jul 21, 2023 at 22:54
  • $\begingroup$ I've been stuck with this all day, my dear Lord, thank you both for clarifying this. I had the definition wrong it seems. $\endgroup$
    – lafinur
    Jul 22, 2023 at 0:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.