HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why DCFL is not closed under kleene star?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whystarcloseddcflkleeneundernot

Problem

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

Solution

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

Context

StackExchange Computer Science Q#58255, answer score: 8

Revisions (0)

No revisions yet.