# 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!

• – User
Commented Sep 30, 2019 at 11:53

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.
• Thank you for the response. I have updated all my states except the accept state to say that neither substring has been seen. I just want to ask if this would be a valid way to do the proof for $q4$? Since the previous string is $01$, adding a $0$ would lead to an accept state in $q5$ since that is a valid substring which hasn't been seen yet whereas with a $1$ we have to restart and go to $q1$ to look for the other substring which begins with $1$. Thank you again! Commented Sep 30, 2019 at 16:28