deterministic finite-state automaton for the language L = {w ∈ {0, 1} ∗ | w does not start with 01 and does not end with 10}.

Question

So I think this is correct but wanted to get a second opinion, but wasn't sure how to test it rather than coming up with strings. Also, it seems a bit complicated, and I was wondering if there was a simpler solution.

Answer 1

You only need six states, representing the following situations:

1. No symbols yet read.

2. One symbol read which is a $0$.

3. The first two symbols are $01$. [Fail]

4. The last symbol is a $1$.

5. The last two symbols are $00$.

6. The last two symbols are $10$. [Fail]

See if you can figure out what the transitions are.