I have the following $DFA$ that recognizes the language containing either a $101$ substring or a $010$ substring.

enter image description here

I need to prove that it accepts exactly the aforementioned language using induction.

This is what I have done so far:

For the base case, an empty string does no contain either of the substrings so the $DFA$ correctly rejects the empty string.

For the induction step, I assume that the $DFA$ is valid for strings of size $n-1$, so assuming that the letter at index $n$ is a $1$ then it rejects accordingly since the string prior may not contain lead to the required substrings, otherwise it gets to state $q5$ and accepts the string. Same thing if the letter at index $n$ is a $0$.

But I feel that this is a bit too simple and I need to split the proof up into multiple parts.

If anyone knows how I should approach this problem, I would greatly appreciate it!


1 Answer 1


I think the most instructive way to do this is to describe what the various states mean.

$q_0$ means that nothing has been read yet.

$q_1$ means that the last character read was $1$ and it is not the case that the last two characters (in order) were $01$. Furthermore, neither the substring $101$ nor $010$ has been seen so far.

$q_2$ means that the last two characters read were $10$ (in that order) and neither of the two distinguished substrings has been seen so far.

The meanings of $q_3$ and $q_4$ are similar, and of course, $q_5$ means that at least one of the distinguished substrings has been seen.

This is easily proved by induction, and it means that the machine will be in $q_5$ if and only if the strings contains one of the two distinguished substrings.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .