Proving a DFA recognizes a language using induction The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction.



So far, I have managed to split each state up was follows:

q0: Nothing has been input yet.

q1: The last letter was a $1$ and the last two characters were not $01$.

q2: The last letter was a $0$ with the letter before that a $1$.

q3: The last letter was a $0$ and the last two characters were not $10$.

q4: The last letter was a $1$ with the letter before that a $0$.

q5: At least one of the two substrings has been seen.

Induction basis: The empty string does not have either of the substrings, so is correctly rejected.

But I am not too sure on how to proceed after this. I do not know how I should split the string up to prove that the $DFA$ is accurate.

If anyone knows how I should proceed with this, I would love some help!
The induction you probably want is to show that a string $w$ ends in state $q_i$ iff it satisfies the property associated to that state.

The basis then is that the empty string, which must end in $q_0$, satisfies the property there.

You should be more precise in some of your properties. In $q_4$, the string ends in 01 as you state, but has never seen any of the special strings, in particular it did not end in 101.