3
$\begingroup$

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Where did you read this? Have you tried expressing any not-deterministic CFL you know in terms of a starred DCFL? $\endgroup$ – Raphael♦ Jun 4 '16 at 16:25
  • 2
    $\begingroup$ @Raphael One example is Problem 2.23 in Sipser 3rd ed.: "Show that the class of DCFLs is not closed under the following operations: a) union, b) intersection, c) concatenation, d) star, e) reversal." $\endgroup$ – David Richerby Jun 4 '16 at 16:31
7
$\begingroup$

The language $\{a^nb^nc^k \mid n,k \ge 1\} \cup \{a^nb^kc^n \mid n,k \ge 1\}$ I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can push the $a$'s, but we do not know when to pop (compare with $b$'s or with $c$'s?)

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.

Now consider $(\{d\} \cup L)^*$.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ And even $\{d\}^* \cdot L$! $\endgroup$ – Raphael♦ Jun 5 '16 at 10:43
  • $\begingroup$ @Raphael True, but that does not help to answer the question, or am I overlooking something? $\endgroup$ – Hendrik Jan Jun 5 '16 at 20:37
  • 2
    $\begingroup$ Nope, but it helped me believe that $(\{d\} \cup L)^*$ is not in DCFL. $\endgroup$ – Raphael♦ Jun 6 '16 at 8:53
  • $\begingroup$ @HendrikJan What does that $d$ prefix do exactly? You say it gives away which part we are in. What do you mean by that? $\endgroup$ – tenepolis Dec 26 '17 at 18:05
  • 1
    $\begingroup$ @tenepolis One half of the language starts with letter $a$, the other half with letter $d$, so the automaton can deterministically decide how it will use its stack to accept the string it reads. Without the $d$ this is no longer possible, the machine has to guess what to store, hence it no longer is deterministic. $\endgroup$ – Hendrik Jan Dec 28 '17 at 18:46

Your Answer

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