proving a step in the proof of regular intersection

Question

Let $L_1$ be a context-free language and $L_2$ be a regular language. Then $L_1 \cap L_2$ is context-free.

Part of a proof given in the book "Formal languages and automata": Let $M_{1}=\left(Q, \Sigma, \Gamma, \delta_{1}, q_{0}, z, F_{1}\right)$ be an npda that accepts $L_1$, $M_{2}=\left(P, \Sigma, \delta_{2}, p_{0}, F_{2}\right)$ be a dfa that accepts $\mathrm{L}_{2}$. We construct a push-down automaton $\widehat{M}=\left(\widehat{Q}, \Sigma, \Gamma, \widehat{\delta}, \widehat{q_{0}}, z, \widehat{F}\right)$ that simulates the parallel action of $M_{1}$ and $M_{2}$ : Whenever a symbol is read from the input string, $\widehat{M}$ simultaneously executes the moves of $M_{1}$ and $M_{2}$. To this end we let $$ \begin{aligned} \widehat{Q} &=Q \times P \\ \widehat{q_{0}} &=\left(q_{0}, p_{0}\right), \\ \widehat{F} &=F_{1} \times F_{2}, \end{aligned} $$ and define $\widehat{\delta}$ such that $$ \left(\left(q_{k}, p_{l}\right), x\right) \in \widehat{\delta}\left(\left(q_{i}, p_{j}\right), a, b\right) $$ if and only if $$ \left(q_{k}, x\right) \in \delta_{1}\left(q_{i}, a, b\right) $$ and $$ \delta_{2}\left(p_{j}, a\right)=p_{l} . $$ In this, we also require that if $a=\lambda$, then $p_{j}=\mathrm{p}_{1}$. In other words, the states of $\widehat{M}$ are labeled with pairs $\left(q_{i}, p_{j}\right)$, representing the respective states in which $\mathrm{M}_{1}$ and $M_{2}$ can be after reading a certain input string. It is a straightforward induction argument to show that $$ \left(\left(q_{0}, p_{0}\right), w, z\right) \vdash_{\widehat{M}}^{*}\left(\left(q_{r}, p_{s}\right), \lambda, x\right), $$ with $q_{r} \in F_{1}$ and $p_{s} \in F_{2}$ if and only if $$ \left(q_{0}, w, z\right) \vdash_{M_{1}}^{*}\left(q_{r}, \lambda, x\right), $$ and $$ \delta^{*}\left(p_{0}, w\right)=p_{s} $$

Now, my question: I am not really sure how to do that "straightforward induction". I thought to do an induction on the length of the string, with the base case being 0. The base case means that we have lambda as our word. For the induction step I thought of assuming that it holds for strings of length n, and proving for strings of length n + 1. Do I have to prove it in both directions separately, or can I do both directions at once? Could someone help me write formally down why this statement is true, even though it seems quite straightforward?

SOLUTION: SOLUTION IN WORDS

For the base case, we have 0 steps. The proof just follows from the definition of what 0 steps actually is (doing nothing).

For the inductive case: We say that the statement holds for steps of length n, and proof for steps of length n + 1. We should not say anything about the length of the strings, so they could be of length 0 or longer. From the induction hypotheses we have everything done and have 1 step left. This step is proven by the definition of $\widehat{\delta}$. For the DFA, I made the distinction between lambda-transition and actually consuming a letter.

Answer 1

In order to prove the statement by induction it has to be generalized somewhat. Observe that the current statement refers to final states of the automata involved. To be able to extend arbitrary computations we will have to consider arbitrary states as last state of the computations, so we consider also non-accepting computations.

Also note that the computation ends with no remaining symbols on the input tape. Also that has to be generalized, as we must be able to read a next symbol. Luckily
$(q_{0}, w, z) \vdash_{M_{1}}^{*} (q_{r}, \lambda, x)$ if and only if $(q_{0}, w{\cdot} u, z) \vdash_{M_{1}}^{*} (q_{r}, u, x)$: the computation does not change if we add more symbols on the input tape.

For the induction it is probably best to use the number of steps used by both pushdown automata. The length of the input word disregards long computations on the empty string possible for a pda.

The inductive step probably strings this together as follows, but I did try not all details.

$$ \left(\left(q_{0}, p_{0}\right), w{\cdot}a, z\right) \vdash_{\widehat{M}}^{\ell}\left(\left(q_{r}, p_{s}\right), a, x\right) \vdash_{\widehat{M}}\left(\left(q'_{r}, p'_{s}\right), \lambda, x'\right) $$ if and only if $$ \left(q_{0}, w{\cdot}a, z\right) \vdash_{M_{1}}^{\ell}\left(q_{r}, a, x\right) \vdash_{M_{1}}\left(q'_{r}, \lambda, x'\right), $$ $$ \delta^{*}\left(p_{0}, w\right)=p_{s},\text{ and } \delta^{*}\left(p_{s}, a\right)=p'_{s} $$

Probably it is best to have "if and only if" in the inductive hypothesis, but in the proof for the additional step check both directions separately, unless upon writing the proof arguments turn out to be symmetric.