1
$\begingroup$

I would like to write a proof of the following statement $ \delta^+(q,PQ) = \delta^+(\delta^+(q,P),Q) $

$\delta^+$ - Extended transition function

I have to do it by induction. However, I'm not sure what I should do. At first, check it for $P = \epsilon$ and $Q = \epsilon$, right? What next?

1 Answers 1

2

You don’t have to worry about $P$: the induction is on the length of $Q$. Your base case is $Q=\epsilon$: check that $\delta^+(q,P\epsilon)=\delta^+(\delta^+(q,P),\epsilon)\;.$ Your induction step will then be to show that if $\delta^+(q,PQ)=\delta^+(\delta^+(q,P),Q)\;,$ then $\delta^+(q,P(Qx))=\delta^+(\delta^+(q,P),Qx)\;,$ where $x$ is any symbol in the input alphabet.

Assuming that $\delta^+$ has been defined by $\delta^+(q,Px) = \delta(\delta^+(q,P),x)$, this shouldn’t be too hard to do.

  • 0
    Ohh.. the last line should be $L = \delta^{+}(q,PQa) = \delta(\delta^{+}(q,PQ),a) = \delta(\delta^{+}(\delta^{+}(q,P),Q),a) = P$ the check is for $|Q| = 0$: $|Q| = 0 \rightarrow Q = \epsilon$ $L = \delta^{+}(q,P\epsilon) = \delta(\delta^{+}(q,P),\epsilon) = \delta^{+}(q,P)$ $P = \delta^{+}(\delta^{+}(q,P),\epsilon) = \delta^{+}(q,P)$ $L = P$2011-10-24