# Shuffle of a DCFL and a regular language

This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability".

The shuffle $$A||B$$ of two languages $$A$$ and $$B$$ is defined as $$\{w \mid w = a_1b_1\ldots a_kb_k,$$ where $$a_1\ldots a_k ∈ A$$ and $$b_1\ldots b_k ∈ B,$$ each $$a_i,b_i ∈ Σ^∗\}$$.

1. Show that if $$L$$ is context-free and $$R$$ is regular, then $$L||R$$ is context-free.
2. If $$L$$ is a DCFL, is $$L||R$$ necessarily a DCFL? Give proof.

The first part is easy by the product construction. I believe that the shuffle of a DCFL and a regular language is not necessarily a DCFL but I am unable to come up with a proof. Any help will be appreciated.

If $$L$$ is a DCFL and $$d$$ a symbol, then $$\{d\}^*{\cdot} L$$ is not necessarily a DCFL. Thus DCFL is not closed under pre-concatenation with regular languages.
The language $$L = \{ a^nb^nc^k \mid n,k \ge 1\} \cup \{d\;a^nb^kc^n > \mid n,k \ge 1\}$$ however, is deterministic. The $$d$$ prefix gives away which part we are in.
It now follows that DCFL are not closed under shuffle with regular $$\{d\}^*$$, as we can intersect that shuffle with regular $$\{d\}^*\{a,b,c\}^*$$ without losing determinism.