I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
$\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
$\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
$\begingroup$
$\endgroup$
Disclaimer
This is a hopefully improved version of the answer of @RAGHAVAMAJJARI. I wrote it to understand what is going on in the proof.
Claim
The Kleene closure of a deterministic context free language DCFL is not a DCFL.
Proof
Let $\newcommand{\lang}{\mathcal L}\lang = \lang_1 \cup \lang_2 = \newcommand{\set}[1]{\left\{#1\right\}}\newcommand{\Nset}{\mathbb N}\set{c a^n b^n \mid n \in \Nset\cup\set 0} \cup \set{ a^mb^{2m} \mid m\in\Nset}$, which is a deterministic context free language thanks to the letter $c$ in front of every word in $\lang_1$. If $\lang^\ast$ is the Kleene closure of $\lang$, any string $x\in\lang^\ast$ should be a concatenated permutation of words $y_i \in \lang$, with the concatenation repeated numerably many times, zero included.
Now let $y_1 = c$ and $y_2 = ab^2$, which are both clearly in $\lang$. This can be seen by letting $n = 0$ and $m = 1$ in the sets $\lang_1$ and $\lang_2$. Because of this, the word $cab^2$ is in $\lang^\ast$, which can again be seen by in the first iteration taking $c$ and on the second iteration taking $ab^2$ from the set and forming a concatenation of these two words.
As both parts of the union that form $\lang$ are DCFLs, they are both recognized by the deterministic pushdown automata (DPA) $A_1$ and $A_2$, which are shown in the two below images respectively. In order to recognize the word $y_1y_2 = cab^2$, you would have to form a new automaton $A = A_1A_2$, by connecting the individual automata appropriately. However, this connection cannot be made deterministically.
Suppose it could. But as demonstrated in the below picture, the only way to recognize the word by combining the two automata $A_1$ and $A_2$ would be to either have a spontaneous transition $\newcommand{\trans}[1]{\overset{#1}{\longrightarrow}} s_1\trans{\epsilon, \sqcup/ \epsilon}t_0$ (where $\sqcup$ is the base symbol used to initialize the stack), or $s_1 \trans{\epsilon, \epsilon / \epsilon} t_1$. This is not deterministic behaviour, as now there is an empty transition out of a state that already has a non-empty transition out of it. This is a contradiction.
Therefore the set of DCFLs is not closed under the Kleene closure. We are therefore done with the proof.
$\begingroup$
$\endgroup$
proving kleene closure of DCFL is not DCFL
-
1$\begingroup$ Could you please transcribe your image into text? You can use LaTeX here. $\endgroup$ – Evil Oct 9 '19 at 14:44
