Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Please don't use the homework tag alone without any other tags. –  sxd Oct 21 '11 at 14:21

1 Answer 1

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|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

 
discard

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.