Why DCFL is not closed under kleene star?

Question

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

Answer 1

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

Answer 2

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.

Answer 3

proving kleene closure of DCFL is not DCFL