2
$\begingroup$

Let the alphabet be $\Sigma=\{0,1\}$. I want to construct a DFA which accepts strings ending with either '110' or '101', additionally there should be only one final state.

I have a solution with more than one final state, but cannot come up with a solution which has only one final state.

$\endgroup$
1
  • 2
    $\begingroup$ How many states do you have and did you split the path when you have successfully read the first 1? Could you state your solution? $\endgroup$
    – dtt
    Commented Feb 10, 2017 at 3:10

2 Answers 2

5
$\begingroup$

There cannot be a single final state. Consider any DFA for the language, and let $\sigma_{110},\sigma_{101}$ be its states after reading $110,101$ (respectively). Clearly $\sigma_{110},\sigma_{101}$ are accepting states. Moreover, they cannot be the same state since $1101$ is in the language but $1011$ is not.

$\endgroup$
0
$\begingroup$

Solution with only one Final state :-

(start)q0 on 0 = qo, (start)q0 on 1 = q1, q1 on 0 = q2, q1 on 1 = q4, q2 on 0 = q0, q2 on 1 = q3, (final)q3 on 0 = q0, (final)q3 on 1 = q1, q4 on 0 = q3, q4 on 1 = q1

$\endgroup$
1
  • 1
    $\begingroup$ This automaton rejects 1101, but it should accept it, since it ends in 101. For 1101, it goes q0 -(1)-> q1 -(1)-> q4 -(0)-> q3 -(1)-> q1, and rejects since q1 is not final. $\endgroup$ Commented Jun 1 at 18:13

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.