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

755 Views Asked by At

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!

1

There are 1 best solutions below

9
On BEST 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$.