0
$\begingroup$

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: enter image description here enter image description here 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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Dear @HendrikJan, Thank you for the answer! It really helped me to get started, but in the base case of the inductive proof, I already got stuck. I tried as base case: number of steps of the NPDAs = 0, so this is only possible if the initial state of M^ is final. So the word 'w' has to be the empty string? But what if the length of the word is not 0, but the machine M^ stopped after 0 steps because there were no more transitions in the final state (initial state here) of the non-determinstic (!) automata? Am I saying weird things here? Should I not talk about the length of the word at all? $\endgroup$
    – Ronald
    Aug 30, 2022 at 18:26
  • $\begingroup$ You do not have to restrict yourself to accepting computations! Any computation of the original PDA M1 merges with a computation of the FA M2 into a new PDA M^. The first component of the merged computation of M^ is the computation of M1, so it should perfectly fit. All that is possible in zero steps should be $(q0,\lambda,z) \vdash^0_{M1} (q0,\lambda,z)$ and $\delta^*(p0,\lambda) = p0$ iff $(q0p0,\lambda,z) \vdash^0_{\hat M} (q0p0,\lambda,z)$. $\endgroup$ Aug 30, 2022 at 18:57
  • $\begingroup$ Thank you! I understand it better now. If I'm right, 'zero steps' means that you can't get to another state? That's why the string to process has to be empty (λ)? I'm a little bit confused about the correlation between 0 steps and empty string. Could you help me with this? $\endgroup$
    – Ronald
    Aug 31, 2022 at 9:51
  • $\begingroup$ In automata and grammars one usually defines some step-relation (one action of the automaton $\vdash$, one derivation step $\Rightarrow$). The actual computation is then zero, one or more steps of this relation, the reflexive transitive closure $\vdash^*$, $\Rightarrow^*$. Zero steps is just the identity, doing nothing, the configuration of the automaton does not change: $(p,w,z) \vdash^0 (p,w,z)$. Same state, no letters read from the tape, no pops from the stack. So yes, with zero steps we have "read" the empty string (but actually we did nothing). $\endgroup$ Aug 31, 2022 at 12:03
  • $\begingroup$ Thank you for the explanation. I used it to prove the statement. I added my solution in pictures and in words. Could you please take a look at it (and at the questions in it), when you got time? Thank you very much in advance! $\endgroup$
    – Ronald
    Sep 2, 2022 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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