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

Exercise Description

We defined latex2png equation by breaking the input string into any string followed by a single symbol (in the inductive part). However, we informally think of latex2png equation 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 latex2png equation. Show that in fact

latex2png equation

for any state q and strings x and y.

Hint: Perform an induction on latex2png equation

Solution

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

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

    latex2png equation

    Applying the definition of latex2png equation in the right part we get:

    latex2png equation

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

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

    latex2png equation

    Now lets see if the hiphotesis hold for the latex2png equation case:

    latex2png equation

    Applying the definition of latex2png equation in the left part we get:

    latex2png equation

    Applying the definition of latex2png equation in the right part we get:

    latex2png equation

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

    latex2png equation

    that is true, so we have finished the proof.

    QED