1

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?

Brian M. Scott
  • 616,228
deem
  • 247

1 Answers1

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.

Brian M. Scott
  • 616,228
  • The assumption is $q_{0}(PQ) = \delta^{+}(\delta^{+}(q_{0},P),Q)$ and the argument is $q_{0}(PQa) = \delta^{+}(\delta^{+}(q_{0},P),Q)a$ $$L=q_{0}(PQa)=\delta(\delta^{+}(q_{0},PQ),a)=\delta(\delta^{+}(\delta^{+}(q_{0},P),Q),a)=\delta^{+}(\delta^{+}(q_{0},P),Q)a=P$$ Is it done right? I used $q_{0}(Pa) = \delta(\delta^{+}(q_{0},P),a)$ – deem Oct 23 '11 at 13:59
  • @user12465: What do you mean by $\delta^+(\delta^+(q_0,P),Q)a$? $\delta^+(\delta^+(q_0,P),Q)$ is a state, say $q_1$, and $q_1a$ doesn’t make sense. Also, $\delta(\delta^+(q_0,PQ),a)$ is a state, while $P$ is an input word, so the two can’t be equal. – Brian M. Scott Oct 23 '11 at 23:49
  • Ohh... I tried to do it like in my notes from the lecture (there was only a proof for P only). OK... maybe it should be like this: the assumption: $$\delta^{+}(q,PQ) = \delta^{+}(\delta^{+}(q,P),Q)$$, the argument: $$\delta^{+}(q,PQa) = \delta(\delta^{+}(\delta^{+}(q,P),Q),a)$$ and the proof: $$L = \delta^{+}(q,PQa) = \delta(\delta^{+}(q,PQ),a) = \delta(\delta^{+}(q,P),Q),a) = P$$ Is is OK now? – deem Oct 24 '11 at 17:56
  • 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$$ – deem Oct 24 '11 at 19:03