Question

(Full disclosure: homework question)

Let $M = (Q, \Sigma, q_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^*$ is defined as follows:

  1. $\forall q \in Q$

    $\delta^*(q, \Lambda) = q$

  2. $\forall q \in Q, y \in \Sigma^*, \sigma \in \Sigma$

    $\delta^*(q, y \sigma) = \delta(\delta^*(q, y), \sigma)$

I am attempting to prove the following statement $\forall x,y \in \Sigma^*$:

$\delta^*(q, xy) = \delta^*(\delta^*(q, x), y)$

It seems pretty obvious from an intuitive standpoint. Since the definition of $\delta^*$ states that for all $y \in \Sigma^*, \sigma \in \Sigma$

$\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)$

And since the base case of $\delta^*$ is (using $\Lambda$ as the empty string)

$\delta^*(q, \Lambda) = q$

That means $\delta^*(q, y)$ is just a bunch of nested $\delta^*$ applications with the first symbol of $y$ on the innermost application, and the last symbol of $y$ on the outermost application. E.g. if $y = y_1y_2y_3$, then

$\delta^*(q, y) = \delta^*(\delta^*(\delta^*(y_1), y_2), y_3)$

I'm not very experienced at writing proofs, so I'm not sure how to go about setting up the basis case, induction hypothesis, etc. I can prove the first equation for $xy = \Lambda$ as the basis, but I don't know what to do beyond that.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top