Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.