1
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 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 Apr 3 '16 at 13:58
  • 1
    $\begingroup$ You have already pretty much proven that that solution is wrong. What more do you need? $\endgroup$ – Raphael♦ Apr 3 '16 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$ – Anton Trunov Apr 3 '16 at 14:22
  • $\begingroup$ As JEP shows, the book contains two typos. What book does not? :-) $\endgroup$ – phs Apr 4 '16 at 11:25
1
$\begingroup$

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\}$}.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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