0
$\begingroup$

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!

  • 0
    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.2012-08-04
  • 0
    @HenningMakholm - $L_i$ is what I think $L(q_i)$ is2012-08-04

1 Answers 1

2

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

  • 0
    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$ ?2012-08-04
  • 0
    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.2012-08-04
  • 0
    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!2012-08-04
  • 0
    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 ..."2012-08-04
  • 0
    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...)2012-08-05
  • 0
    @Belgi: Yes, that's why I had to use the fuzzy wording "describe" about the bullets rather than "is true". What I mean is that **either** the machine ends in $q_2$ and $w$ contains $\mathtt aa$, **or** the machine ends in $q_1$ and $w$ does not contain $\mathtt aa$ but ends with $\mathtt a$, **or** the machine ends in $q_0$ and $w$ neither contains $\mathtt aa$ nor ends with $\mathtt a$.2012-08-05
  • 0
    I'm sorry I coldn't review this answer for this long, I tried to do the following (using the help I got from you): I replaced the "if and only if" in the bullets to "and", then I wrote that we are proving that this bullets descrive every word (and I am using the word describe for the same reason you were). I did the base case for length=$0$, than I wrote $w=x\sigma$ and devided to $3 $cases by $x\in L(q_1)$, or in $L(q_2),L(q_3)$. then I divided each cases to two cases by $\sigma = a$ or $\sigma = b$2012-08-19
  • 0
    Since I know to what state the automata goes to after reading $x$ (by assumption) I know by dividing to the cases of $\sigma = a,b$ where the automata goes to after reading $w$ and I showed that the part after "and" in the description of the bullets also holds true. I concluded by writing that $L$ is all the words that are not in $L(q_2)$ hence all the words that don't contain $aa$ as a subword. Does this sound OK to you ? thank you again for your time and help!2012-08-19
  • 0
    Sounds alright to me, assuming an appropriate meaning for $L(q_i)$. Formally what you're doing is to rewrite the induction property from "$(q_0\Leftrightarrow P)\land(q_1\Leftrightarrow Q)\land(q_2\Leftrightarrow R)$" to "exactly one of $q_0\land P$ or $q_1\land Q$ or $q_2\land R$", which is logically equivalent, because you already know that exactly one of $q_0$, $q_1$ and $q_2$ will be true.2012-08-19