3
$\begingroup$

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

$\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
2
$\begingroup$

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.

enter image description here enter image description here

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.

enter image description here

Therefore the set of DCFLs is not closed under the Kleene closure. We are therefore done with the proof.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

enter image description here proving kleene closure of DCFL is not DCFL

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Could you please transcribe your image into text? You can use LaTeX here. $\endgroup$ – Evil Oct 9 '19 at 14:44

Your Answer

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