# How to prove that the language of a DFA is some $L$

Consider the following 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!

-
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

## 1 Answer

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

-
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