1
$\begingroup$

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

enter image description here

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Dev SR Sep 30 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.