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 as follows:
$q_0$: Nothing has been input yet.
$q_1$: The last letter was a $1$ and the last two characters were not $01$.
$q_2$: The last letter was a $0$ with the letter before that a $1$.
$q_3$: The last letter was a $0$ and the last two characters were not $10$.
$q_4$: The last letter was a $1$ with the letter before that a $0$.
$q_5$: 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 in $q0$.
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!
You should induct on the length of the input string!
Let $\mathcal{L}$ be the language recognized by this DFA, and write $x \sqsubseteq y$ for $x$ is a substring of $y$.
If the input ($x$) has length 0, 1, or 2, then:
Now if the input has length 3:
$ x \in \mathcal{L} \iff x = 101 \text{ or } 010 \iff 101 \text{ or } 010 \sqsubseteq x $
Now, inductively, say $x \in \mathcal{L} \iff 101 \text{ or } 010 \sqsubseteq x$. What can we say about $x0$ and $x1$? Here we should use the cases that you've mentioned! What we do with $x0$ and $x1$ will depend on the last few digits of the string.
I hope this helps ^_^