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!