Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following DFA: DFA

It is quite clear that the language of this FDA is all the words that don't have the word $aa$ as a subword.

My question is: How can I formally prove that this is the language of this FDA ?

My efforts: I tried to determine $L(q_0)$ and $L(q_1)$ (that we denote as $L_0$ and $L_1$ accordingly) and prove that these are indeed what I determined using induction (this is the type of method used in the book I am studing from), I had some problems determining $L(q_0)$ and $L(q_1)$ and I am not sure if I should show equality 'straight out' or should I do two proofs showing $L(q_i)\subset L_i$ and $L_i\subset L(q_i)$.

Help is very much appreciated!

share|cite|improve this question
You won't get anything out of showing $L(q_i)\subseteq L_i$, because you have defined $L_i$ to mean $L(q_i)$, so $L(q_i)\subseteq L_i$ is the same as $L(q_i)\subseteq L(q_i)$, which is true but not very useful. – Henning Makholm Aug 4 '12 at 1:37
@HenningMakholm - $L_i$ is what I think $L(q_i)$ is – Belgi Aug 4 '12 at 1:39
up vote 2 down vote accepted

Show by induction on the length of $w$ that the state of the machine after reading $w$ is

  • $q_2$ if and only if $w$ does contain $\mathtt{aa}$
  • $q_1$ if and only if $w$ does not contain $\mathtt{aa}$, but ends with an $\mathtt{a}$.
  • $q_0$ if and only if $w$ does not contain $\mathtt{aa}$ and does not end with an $\mathtt{a}$.

The base case is trivial -- the empty word neither contains $\mathbb{aa}$ nor ends with an $\mathtt{a}$, which matches the initial state $q_0$.

In the induction case we either have $w=v\mathtt{a}$ or $w=v\mathtt{b}$, and in each of these cases simply consider the three subcases that tell what happens with $v$.

For example, in the subcase where $w=v\mathtt{a}$ and the machine ends in $q_1$ after reading $v$, the induction hypothesis says that $v$ must end with an $\mathtt{a}$. But then $v\mathtt{a}$ ends with two $\mathtt{a}$s, so $w=v\mathtt{a}$ certainly contains $\mathtt{aa}$. And that matches the fact that reading $\mathtt{a}$ in state $q_1$ lands us in $q_2$.

share|cite|improve this answer
I'm not sure what you showed in the last paragraph (although I agree that it's correct). To what subcases did you divide ? are there $3$ subcases for each of the two subcases $w=va$ and $w=vb$ ? – Belgi Aug 4 '12 at 1:47
Yes, there are 3 subcases for each of $w=v\mathtt a$ and $w=v\mathtt b$. Each of these corresponds to one of the bullets in the induction hypothesis, since effectively what the induction hypothesis says is that one of these bullets describe both $v$ and the state the machine is in after reading $v$. The last paragraph shows the reasoning for one of the $2\times 3$ subcases; it is meant to be supplemented with 5 more-or-less similar paragraph for the other cases. – Henning Makholm Aug 4 '12 at 1:55
So it's not $2$ cases for each bullet (that is, it's not that $2$ cases shows bullet $1$, $2$ cases show bullet $2$ etc') but rather we show all cases and then deduce bullets $1-3$ alltogether ? thank you for your time and help! – Belgi Aug 4 '12 at 2:03
You can order the work either way, according to what you like best. Either: "First assume that $w=v\mathtt a$. Then by the induction hypothesis one of the following bullets will be true about $v$ ..." or: "Let $v$ be $w$ except for the last symbol. Then by the induction hypothesis one of the bullets will be true about $v$. In the first one $v$ contains $\mathtt{aa}$ and the next-to-last state is $q_2$. We may then have either $w=v\mathtt a$ or $w=v\mathtt b$. In the former case $q_2$ goes to $q_2$ on $\mathtt a$, and $w=v\mathtt a$ must contain $\mathtt{aa}$ because $v$ does ..." – Henning Makholm Aug 4 '12 at 2:09
I gave this some more thought, you wrote "the induction hypothesis says is that one of these bullets describe...". shouldn't this be that all the bullets are true ? (two will be of the form False$\iff$False. So what exactly are we proving, that one of them is true or all of them ? (if it is all of them then I think that we need to add more cases...) – Belgi Aug 5 '12 at 1:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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