# Construct DFA accepting strings ending with '110' or '101'

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.

• 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? – dtt Feb 10 '17 at 3:10

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.