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

Why are DCFL not closed under concatenation or Union whereas CFL is?

Submitted by: @import:stackexchange-cs··
0
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 ?

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.