1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

An example of that is given in a related answer Why DCFL is not closed under kleene star? (see the comment by Raphael below that answer!)

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.

$\endgroup$

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.