0
$\begingroup$

Let $A$ be a DFA and $q$ a particular state of $A$, such that $\delta(q, a) = q$ for all input symbols $a$. Show by induction on the length of input that for all strings $w$, $\delta^* (q, w) = q$.

I'm completely new to the subject. But this is what I have done. Can someone please tell me if this is the correct solution?

For the basis of the induction $|w|=1$, $\delta (q,a)=a$ is already correct by definition.

Let $n = |w|$, the number of symbols in the string $w$. Let $\delta^*(q,w)=q$ be true for some $n \gt 1$ (hypothesis of induction). Now I should prove it for $n+1$ using the hypothesis of induction. Let $z=wa$.

$$ \delta^*(q,z) = \delta^*(q,wa) $$

It follows that: $$ \delta^*(q,wa) = \delta^*(\delta^*(q,w),a) $$

From the hypothesis, I know that $\delta^*(q,w)=q$, so if I substitute this in the above equation:

$$ \delta^*(q,a) $$

and this is equal to $q$ according to the base case. So, I conclude that $\delta^*(q,w)=q$ is true for every $n$.

Is the above so-called "solution" correct?

$\endgroup$
  • 2
    $\begingroup$ I'd say it is mostly correct. You have identified the reason why the result holds and you use the definition of $\delta^*$ at the right place. The logic of the proof could be made clearer. For example, make it clear that you prove for all $z$ of length $n+1$, and that $w$ is not chosen before $z$. Also you want to include words of length $0$. $\endgroup$ – phs Nov 12 '15 at 7:07
  • 1
    $\begingroup$ @phs, Thank you very much for the explanation. Please post it as an answer too, if you like, so I can accept it and future readers could find it easily. $\endgroup$ – Javad Kouhi Nov 12 '15 at 7:26
  • 4
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – Raphael Nov 12 '15 at 8:24
  • $\begingroup$ @Raphael, Thank you for the point, I will keep that in my mind for the next time. But in regard to the current question, I really don't know what should I do now, as I got my answer and everything is now clear, thanks to phs. $\endgroup$ – Javad Kouhi Nov 12 '15 at 10:31
  • $\begingroup$ I think your request for @phs to add an answer is the most reasonable at this point. $\endgroup$ – Raphael Nov 12 '15 at 10:54
5
$\begingroup$

By popular request, here is what the proof could look like:

By induction over the length of $w$. Assume $\delta(q,a)=q$ for all $a$. Take any $w$. There are two cases:

  1. If $|w|=0$ then $w=\epsilon$ (the empty word). Now the definition of $\delta^*$ has "$\delta^*(q,\epsilon)=q$" without any assumption on $\delta$ or $q$. We thus have $\delta^*(q,w)=q$ in this first case.

  2. If $|w|>0$ then $w$ is some $w'a$ and $|w'|<|w|$. Now $\delta^*(q,w)=\delta^*(q,w'a)=\delta(\delta^*(q,w'),a)$ by definition of $\delta^*$. Since $|w'|<|w|$ we have $\delta^*(q,w')=q$ by induction hypothesis. Finally $\delta^*(q,w)=\delta(q,a)$, which is $q$ by the assumption. We have proved the required conclusion in this second case too.

All cases have been covered. The proof is complete.

Note that the two cases can be considered in any order we like. And that we do not use that $|w'|=|w|-1$, just that $|w'|<|w|$.

As you can see, the above proof uses the same arguments as in your solution, and at the same places. It is slightly more rigorous on the quantifications ("take any $w$" is a "$\forall w$" and "$w$ is some $w'a$" is a "$\exists w'\exists a:w=w'a$") and their nesting ($w'$ and $a$ depend on $w$).

It is the kind of proof I'd love to get from a bright student beginning automata theory. But it is too pedantic and pedestrian for experts who, in their own papers, will usually just state the conclusion as obvious from the assumption. They may even not state the conclusion at all and use it anyway.

$\endgroup$
  • $\begingroup$ I follow everything until, "Finally $\delta^*(q,w)=\delta(q,a)$, which is > $q$ by the assumption"...do we know this is true because $a$ is the last symbol of w? Or by definition of $\delta$? $\endgroup$ – maddie Feb 14 '18 at 0:00
  • $\begingroup$ we know it by the assumption: we are told that in this DFA q is such that δ(q,a)=q for all a. $\endgroup$ – phs Feb 15 '18 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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