4
$\begingroup$

It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example: $$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n \mid m,n \ge 1 \right\} = \left\{ a^ib^ic^i \mid i \ge 1 \right\} \not \in \mathcal{L_2},$$ where $L_1,L_2 \in \mathcal{L2}$.

I was wondering if this could be proven using the synchronous parallel composition of two (non-deterministic) PDAs, or rather what is wrong with the following construction which seemingly comes to the opposite conclusion:

Let $PDA_1, PDA_2, PDA_{1,2}$ be, WOLOG, (non-deterministic) PDAs accepting by final state and with total transition functions: $$ PDA_1 = \Big(Q_1, \Sigma_1, \Gamma_1, \delta_1, q^0_1, \gamma^0_1, F_1 \Big) \\ PDA_2 = \Big(Q_2, \Sigma_2, \Gamma_2, \delta_2, q^0_2, \gamma^0_2, F_2 \Big) \\ PDA_{1,2} = \Big(Q_1 \times Q_2 \cup \big(q_{\emptyset}, q_{\emptyset}\big), \Sigma_1 \cup \Sigma_2, \Gamma_1 \times \Gamma_2, \delta_{1,2}, \big(q^0_1, q^0_2 \big), \big(\gamma^0_1, \gamma^0_2 \big), F_1 \times F_2 \Big)$$ where $q_{\emptyset} \not\in Q_1 \cup Q_2$ and $\delta_{1,2}$ is defined as follows: $$ \delta_{1,2} \Big(\big(q_1, q_2 \big), a, \big(\gamma_1, \gamma_2 \big) \Big) = \begin{cases} \Big(\big(q'_1, q'_2 \big), \big(\gamma'_1, \gamma'_2 \big) \Big) & \big(q'_1, \gamma'_1 \big) \in \delta_1 \big(q_1, a, \gamma_1 \big) \land \\ & \big(q'_2, \gamma'_2 \big) \in \delta_2 \big(q_2, a, \gamma_2 \big) \\ & \text{(if such transitions are defined)} \\ \Big(\big(q_{\emptyset}, q_{\emptyset} \big), \big(\gamma_1, \gamma_2 \big)\Big) & \text{otherwise} \\ \end{cases} $$

Surely $PDA_{1,2}$ accepts only words from the intersection of languages $L(PDA_1)$ and $L(PDA_2)$. Why doesn't it accept all of them?

$\endgroup$
4
$\begingroup$

This doesn't work, because the stacks of the two PDAs aren't synchronized. You can get to a state where $\text{PDA}_1$ pushes a symbol but $\text{PDA}_2$ pops a symbol. What is $\text{PDA}_{1,2}$ supposed to do at that point? It's screwed.

The product construction would work if there was a guarantee that the length of the stack of $\text{PDA}_1$ was always the same as the length of the stack of $\text{PDA}_2$ -- but as explained, this is not guaranteed.

Another way to put it: Your definition of $\delta_{1,2}$ does not make any sense. The output is supposed to be an element of $Q \times \Gamma^*$, where here $\Gamma = \Gamma_1 \times \Gamma_2$. However, a pair like $(\lambda'_1,\lambda'_2)$ is not an element of $(\Gamma_1 \times \Gamma_2)^*$. If the length of $\lambda'_1$ was the same as the length of $\lambda'_2$, you could interpret $(\lambda'_1,\lambda'_2)$ as an element of $(\Gamma_1 \times \Gamma_2)^*$: it is the string whose $i$th symbol is $(\lambda'_1[i],\lambda'_2[i])$. Unfortunately, when the length of $\lambda'_1$ is different from the length of $\lambda'_2$, there's no way to interpret $(\lambda'_1,\lambda'_2)$ as an element of $(\Gamma_1 \times \Gamma_2)^*$. Consequently, your definition of $\delta_{1,2}$ is not well-formed: it does not have the proper type signature.

As you quite accurately summarize the situation: One stack can grow ad infinitum while the other not and in order to access the previous element from the shorter stack, the PDA would need to indestructibly go through the potentially infinitely long stack. This could be fixed if we had an automaton with two separate stacks; however, such an automaton would be computationally equivalent to a Turing machine and thus is more powerful than a PDA (which only has one stack).

$\endgroup$
  • 1
    $\begingroup$ Oh, I see. I had not thought about the stack element length. One stack can grow ad infinitum while the other not and in order to access the previous element from the shorter stack, the PDA would need to indestructibly go through the potentially infinitely long stack. This, however, could only be made using e.g. two separate stacks and such automaton would be computationally equivalent to a Turing machine. Thank you for your explanation. $\endgroup$ – Kyselejsyreček Jun 17 '15 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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