1
$\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
    $\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 Feb 10 '17 at 3:10
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$

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.