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
    @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
    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