patternMinor
Why DCFL is not closed under kleene star?
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)^*$.
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.