0
$\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
    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)$2011-10-23
  • 0
    @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.2011-10-23
  • 0
    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?2011-10-24
  • 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