Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 8 down vote accepted

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.

share|cite|improve this answer
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

Explain how, given a PDA for a L1 and a PDA for L2, you can construct a PDA for the concatenation L1L2.?
Answer: The basic answer is to take the accept state for L1, and make it
the start state for L2. However – if L1 leaves symbols on the stack
(other than delta), we might have to pop them. It is not required the stack be empty at accept. So we need a non-deterministic pop to clear
out the stack. Solution on right

share|cite|improve this answer
Because a certain construction does not yield a deterministic PDA, this does not mean that no such PDA exists. "Proofs" of this type are a common error in HW exercises like this. – frafl Jun 4 '13 at 16:04
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 '13 at 16:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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