3
$\begingroup$

The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of limit in DFA (deterministic finite automaton).

I have doubt between two awnsers which are:

  1. It depends on the language and is not possible for every DFA.

  2. Yes we can.

If the answer is positive then how ?

$\endgroup$

1 Answer 1

15
$\begingroup$

It is possible. You just need to duplicate the start state, one copy becoming the starting state with no in-edge, the other copy becoming a state that can have in-edges.

Formally, if $A = (Q, \delta, q_0, F)$ is a DFA, then consider $B = (Q', \delta', q_0', F')$ with:

  • $Q' = Q\cup \{q_0'\}$;
  • $F' = F$ if $q_0\notin F$, or $F' = F\cup \{q_0'\}$ otherwise;
  • for $q\in Q$ and $a\in \Sigma$, $\delta'(q, a) = \delta(q, a)$;
  • for $a\in \Sigma$, $\delta'(q_0', a) = \delta(q_0, a)$.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.