I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
3
$\begingroup$
$\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$
$\endgroup$
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)^*$.
-
3
-
$\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
