# why are deterministic PDAs not closed under concatenation?

I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one. But can someone prove this with an example. Also prove that the resulting language cannot be accepted by DPDA

-

Pick the languages:

$L_1 = \{a^ib^jc^k | i \neq j \}$ and $L_2 = \{a^ib^jc^k | j \neq k\}$; both are DCFL and $L_3 = 0L_1 \cup L_2$ is DCFL, too.

$L_0 = 0^*$ is DCFL (regular)

But $L_{conc} = L_0 \cdot L_3 = 0^* L_3$ is not DCFL.

Proof: Suppose that $L_{conc}$ (which is the concatenation of two DCFLs) is DCFL.

If we intersect $L_{conc}$ with the regular language $0a^*b^*c^*$, we should get a DCFL language:

$L_{conc} \cap \{0a^*b^*c^*\}$ = $0L_1 \cup 0L_2$. suppose $0L_1 \cup 0L_2$ is a DCFL, so $L_1 \cup L_2$ should be a DCFL, too but:

$L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}} = \overline{\{a^ib^ic^i\}}$ which is not DCFL $\Rightarrow$ contradiction.

-
Nice one!! Thanks. Also just to be sure $\overline{\{a^ib^ic^i\}}$ is not a DCFL because they are closed under complement, which would imply there is a DCFL that accepts ${\{a^ib^ic^i\}}$ –  emmy Dec 11 '12 at 16:13
@emmy: yes, DCFLs are closed under complementation –  Vor Dec 11 '12 at 17:25
This proof isn't quite right, since it's entirely possible that two deterministic PDAs can be concatenated so that it's not necessary to pop any symbols at all, even if one or both leaves symbols on the stack. Suppose each PDA leaves a symbol $Z_1$ on the stack (bottom of the stack is $Z_0$ for both). As long as they treat $Z_1$ like $Z_0$, there is no need to pop the $Z_1$. While your proof may work given some extra conditions, we do lose generality by imposing those conditions, so this isn't a complete and correct answer to the question. –  Patrick87 Jun 4 at 16:14