This exercise comes from Introduction to Automata Theory, Languages, and Computation, Second Edition, by Hopcroft, Motwani and Ullman.

Exercise Description

Show that for any state q, string x, and input symbol a, .

Hint: Use Exercise 2.2.2.

Solution

We can proceed by induction in the length of the string x as follows.

• Basis: Consider the case where

Given that and applying the definition of several times in both sides of the equation we get:

So the hipothesis hold for the basis case.

• Induction: Given that we assume that the following sentence is true:

  Now lets see if the hipothesis hold for the case:

  

  Applying the result of Exercise 2.2.2 in the left side of the equation we get:

  

  QED