automatafinite-automatadfa

Create a DFA that contains "11" or ends with "10"

I'm trying to construct a DFA (binary only) that contains "11" or ends with "10".

I tried to do the following:

$q2$ and $q3$ are accepting states

State 0 1
$q0$ $q0$ $q1$
$q1$ $q3$ $q2$
$q2$ $q3$ $q2$
$q3$ ??? ???
  • This is what I've done so far.
  • From q0, if we read 0 we stay in q0, else if we read 1 we go to q1.

  • From q1, if we read 0 we can go to q3 and q3 is accepting state (so it ends with 10), else if we read 1 we go to accepting state q2, and it contains 11.
  • From q2, if we read 1 we can stay in q2, if we read 0 we can go to q3, or should I change it?
  • In q3, I'm not sure.
    • Solution

  • I would first clarify exactly what the states were, then it should become clear what each input value does. The count item is the number of characters we have previously processed (starting at zero), so we can combine states in the initial stages:

    State Explanation) 0 1
    $q0$ count = 0 or previous is 0 $q0$ $q1$
    $q1$ (count = 1 and previous is 1) or (previous two are 01) $q3$ $q2$
    $q2$ have encountered 11 $q2$ $q2$
    $q3$ previous two are 10 $q0$ $q1$

    In other words, if you end up in state $q2$ or $q3$, you have satisfied the DFA end conditions (either 11 was found or it ends with 10).

    Once you enter state $qq2$, any further input is irrelevant since you've just encountered 11. So, in that case, you simply stay in that state while "draining" the remaining digits (or you could ignore any future digits and just "exit" the DFA).

    If you find yourself in state $qq3, it means the previous two digits were 10 and there may or may not be more digits. In that case:

    A diagram to display this is shown below for those more graphically minded: enter image description here