patternMinor
Why are DCFL not closed under concatenation or Union whereas CFL is?
Viewed 0 times
whycflconcatenationareunioncloseddcflunderwhereasnot
Problem
I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves Union is not possible.
However, DCFL is a proper subset of CFL (unambiguous) and CFL is closed under union and concatenation. So how can a proper subset not inherit the global properties of its parent set ?
However, DCFL is a proper subset of CFL (unambiguous) and CFL is closed under union and concatenation. So how can a proper subset not inherit the global properties of its parent set ?
Solution
DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily deterministic CFL.
Context
StackExchange Computer Science Q#82353, answer score: 9
Revisions (0)
No revisions yet.