# Why DCFL is not closed under kleene star?

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

• Where did you read this? Have you tried expressing any not-deterministic CFL you know in terms of a starred DCFL? – Raphael Jun 4 '16 at 16:25
• @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." – David Richerby Jun 4 '16 at 16:31

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)^*$.

• And even $\{d\}^* \cdot L$! – Raphael Jun 5 '16 at 10:43
• @Raphael True, but that does not help to answer the question, or am I overlooking something? – Hendrik Jan Jun 5 '16 at 20:37
• Nope, but it helped me believe that $(\{d\} \cup L)^*$ is not in DCFL. – Raphael Jun 6 '16 at 8:53
• @HendrikJan What does that $d$ prefix do exactly? You say it gives away which part we are in. What do you mean by that? – tenepolis Dec 26 '17 at 18:05
• @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. – Hendrik Jan Dec 28 '17 at 18:46 proving kleene closure of DCFL is not DCFL

• Could you please transcribe your image into text? You can use LaTeX here. – Evil Oct 9 at 14:44