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

| cite | improve this question | | | | |

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.

| cite | improve this answer | | | | |
  • 1
    $\begingroup$ 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\}}$ $\endgroup$ – e_noether Dec 11 '12 at 16:13
  • $\begingroup$ @emmy: yes, DCFLs are closed under complementation $\endgroup$ – 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

| cite | improve this answer | | | | |
  • $\begingroup$ 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. $\endgroup$ – frafl Jun 4 '13 at 16:04
  • $\begingroup$ 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. $\endgroup$ – Patrick87 Jun 4 '13 at 16:14

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.