5
$\begingroup$

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

$\endgroup$

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
2
  • 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, 2012 at 16:13
  • 1
    $\begingroup$ @emmy: yes, DCFLs are closed under complementation $\endgroup$
    – Vor
    Dec 11, 2012 at 17:25
-2
$\begingroup$

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

$\endgroup$
2
  • $\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, 2013 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, 2013 at 16:14

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.