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

Exercise Description

We defined by breaking the input string into any string followed by a single symbol (in the inductive part). However, we informally think of as describing what happens along a path with a certain string of labels, and if so, then it should not matter how we break the input string in the definition of . Show that in fact

for any state q and strings x and y.

Hint: Perform an induction on

Solution

As suggested by the authors we proceed to proof using induction in the length of y.

• Basis: Lets We show that the hipothesis is true for this case:

  

  Applying the definition of in the right part we get:

  

  that is true, so the hiphotesis hold for the basis case.

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

  

  Now lets see if the hiphotesis hold for the case:

  

  Applying the definition of in the left part we get:

  

  Applying the definition of in the right part we get:

  

  Finally we apply the induction case for in the left part and we get:

  

  that is true, so we have finished the proof.

  QED