1
$\begingroup$

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\}^*\}$

DFA

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.
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Mar 24 '15 at 0:03
  • $\begingroup$ possible duplicate of How do I write a proof using induction on the length of the input string? $\endgroup$ – D.W. Mar 24 '15 at 0:06
  • $\begingroup$ 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). $\endgroup$ – D.W. Mar 24 '15 at 0:06
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – babou Mar 24 '15 at 11:06
  • $\begingroup$ @babou I was not criticizing your answer in any way. I was just offering an alternative proof. $\endgroup$ – J.-E. Pin Mar 24 '15 at 11:27
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ $P_1(u)$ is $u=xa$ and $P_2(u)$ is $u=xb$? $\endgroup$ – Lee Mar 24 '15 at 6:45
  • $\begingroup$ @Lee This is correct for $P_1$, but you need more for $P_2$. $\endgroup$ – babou Mar 24 '15 at 8:24
  • $\begingroup$ 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$. $\endgroup$ – Lee Mar 24 '15 at 8:51
  • $\begingroup$ @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? $\endgroup$ – babou Mar 24 '15 at 9:08
  • $\begingroup$ @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. $\endgroup$ – babou Mar 24 '15 at 9:19

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.