Problem Detail: 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
Asked By : emmy
Answered By : Vor
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7325
