# Prove correctness of DFA ending with ab

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$

I know that I need to prove by induction on the length of the word but I am not sure how to do the induction step.

My try:

Anchor: After processing the only string of length zero, ε, the automaton is in state $q_0$ as claimed.

Hypothesis: After reading a string u the automaton is in state $q_1$ iff $u=xa$, and in state $q_2$ iff $u=xab$ and in $q_0$ iff $u=ε$ or $u=xb$. The claim holds for input fragments of length up to n.

Step: Any string $v$ of length $n+1$ is either $v=ua$ or $v=ub$

We split to cases:

1. $v=ua$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q_0$ or $q_2$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted. Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted.
2. $v=ub$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q_0$ or $q_2$ - there for if we call $b$ after that we get to $q_0$ so $ub$ is not accepted. Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $b$ after that we get to $q_2$ so $ua$ is accepted.
• What have you tried? Where did you get stuck? Have you read other examples in your textbooks? We expect you to do a significant amount of research/self-study on your own before asking, and to tell us in the question what you've tried -- what research have you done? – D.W. Mar 24 '15 at 0:03
• possible duplicate of How do I write a proof using induction on the length of the input string? – D.W. Mar 24 '15 at 0:06
• See also cs.stackexchange.com/q/11315/755 for how to do this with a grammar (you could in principle apply those techniques if you converted the DFA to a regular grammar, though that'd be a harder path). – D.W. Mar 24 '15 at 0:06

There is no induction needed. There is only one transition reaching the final state $q_2$, namely $q_1 \xrightarrow{b} q_2$. Furthermore, every transition reaching $q_1$ is labelled by $a$. It follows that every word accepted by the automaton has to end by $ab$. It remains to prove that, conversely, any word of the form $uab$ is accepted. After reading $u$ from the initial state $q_0$, you reach one of the three states $q_0$, $q_1$ or $q_2$. It suffices now to observe that $q_0 \xrightarrow{ab} q_2$, $q_1 \xrightarrow{ab} q_2$ and $q_2 \xrightarrow{ab} q_2$. Thus $q_0 \xrightarrow{uab} q_2$ in all cases, which means that $uab$ is accepted.
• Of course, one does not need industion, since whatever happens with the first $n-2$ symbols is immaterial. But the OP was specific about using induction. So I tried to give it an inductive look in my answer, considering that (though not ncessary here) induxtion is often useful in other cases. – babou Mar 24 '15 at 11:06
The induction hypothesis can look like: "after reading a string $u$ the automaton is in state $q_1$ iff $P_1(u)$, and in state $q_2$ iff $P_2(u)$." I leave it to you to determine what are the properties $P_1$ and $P_2$.
• $P_1(u)$ is $u=xa$ and $P_2(u)$ is $u=xb$? – Lee Mar 24 '15 at 6:45
• @Lee This is correct for $P_1$, but you need more for $P_2$. – babou Mar 24 '15 at 8:24
• Well, you get to $q_2$ after you have $b$ in $q_1$ or $ab$ from $q_0$. But I guess I don't understand where I use the hypothesis for $n-1$. – Lee Mar 24 '15 at 8:51
• @Lee Your suggestion that $P_2(u)$ is $u=xb$ is not incorrect, but it is not sufficient. You know more about the string $u$ when you reach state $q_2$. By the way, have you been actually asked to use recursion or is it your idea to us it? – babou Mar 24 '15 at 9:08
• @Lee The way you use the induction hypothesis is as follow. You prove that if the induction hypothesis is verified for all strings of length $p$, such that $p\leq n$, then it must also be true for any string $v$ of length $n+1$. You proceed here by considering that any string $v$ of length $n+1$ is either $v=ua$ or $v=ub$, and you use the induction hypothesis for $u$ to prove that it is also verified for $v$, in each case. – babou Mar 24 '15 at 9:19