1
$\begingroup$

I have found various opinions saying they are (a link to one is given in D.W.'s comment). However, a proof that DCFLs themselves are not closed under concatenation found here on StackExchange seems to be applicable also to concatenation with regular languages:

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.

($\{a^ib^ic^i\}$ is not DCFL and the class is closed under complement.)

Is there a reason why the presented disproof wouldn't apply to concatenation with regular languages and if so, is there a more understandable proof of the closure then the one referenced?

$\endgroup$
  • 1
    $\begingroup$ I don't understand what you're trying to prove. Your title says you want to prove that DCFLs are closed under concatenation. Your question seems to say you want to prove they're not closed. What are you trying to prove? What research have you done? For instance, it is known that the DCFLs are not closed under concatenation, so if you're trying to prove they are, you probably aren't going to succeed. See, e.g., planetmath.org/closurepropertiesonlanguages. However, the concatenation of a DCFL and a regular language is a DCFL. So what are you trying to prove? $\endgroup$ – D.W. Jun 21 '15 at 1:16
  • 2
    $\begingroup$ See also cs.stackexchange.com/a/13215/755, which cites a paper giving a proof of some of these properties -- does that paper answer your question? $\endgroup$ – D.W. Jun 21 '15 at 1:17
  • $\begingroup$ I am sorry, this is obviously my fault. I got a notion that the proof of DCFLs not being closed under concatenation seems to be applicable also to concatenation with a regular language so I tried to disprove the closure. As I was later searching for support of my conclusion, I found some opinions saying the contrary, although I could not find any erroneous assumption in my proof. Thank you for the reference you have mentioned. It may, however, take me some time until I understand the proof since I am not even familiar with the constructions the author uses in the 3.3 theorem. $\endgroup$ – Kyselejsyreček Jun 21 '15 at 12:10
  • 2
    $\begingroup$ Isn't the confusion about which side you concatenate? If $L$ is a DCFL and $R$ is regular, then $LR$ is DCFL, wheras $RL$ is not necessarily DCFL (as seen in the example you link). $\endgroup$ – Hendrik Jan Jun 21 '15 at 23:14
  • $\begingroup$ I thought I'd check back in. Did the comments (e.g., Hendrik's comment) answer your question? If so, I encourage you to post an answer below that contains a complete answer to your own question -- who knows, it might be useful to others, and it helps indicate in the system that the question has been answered. If not, I encourage you to edit the question to clarify what your remaining confusion/uncertainty/question is. $\endgroup$ – D.W. Jun 22 '15 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.