For the following finite state machine:

enter image description here

The language recognized by it is given to be: $0+(10+11)(0+1)^*$ in my samples book, which I think is clearly wrong, since there's no return path to the final state.

I think the language recognized should be just an epsilon or nothing. I wanted to confirm if I am right or wrong with the answer.

  • 4
    $\begingroup$ You may only consider there is a typo in your book and that the final state should be $C$. But then the language recognized by the automaton should be $(0+(10+11))(0+1)^*$. $\endgroup$
    – J.-E. Pin
    Commented Apr 3, 2016 at 13:58
  • 1
    $\begingroup$ You have already pretty much proven that that solution is wrong. What more do you need? $\endgroup$
    – Raphael
    Commented Apr 3, 2016 at 14:04
  • $\begingroup$ Considering your analysis of the automaton with the typo: "...an epsilon or nothing". If a finite automaton represents the empty language then all its accepting states must be unreachable from the start state, and this is clearly not the case here. $\endgroup$ Commented Apr 3, 2016 at 14:22
  • $\begingroup$ As JEP shows, the book contains two typos. What book does not? :-) $\endgroup$
    – phs
    Commented Apr 4, 2016 at 11:25

1 Answer 1


Yes, you are right.

As given FA is DFA. It is accepting string only $\{\epsilon \}$.

And, complement of given DFA accepting : $\implies (1+0+1(0+1))(0+1)^*= (1+0+(10+11))(0+1)^*$

$\implies 1(0+1)^*+0(0+1)^*+(10+11)(0+1)^* = (0+1)^+ =$ { accepting everything other than $\{\epsilon \}$ string over alphabet $\{0,1\}$}.


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.