2
$\begingroup$

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 ?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

The fact that is a proper subset does not inherit the global properties in general is common in mathematics and computer science. A proper subset does not have to inherit the global properties of its superset.

For example, the set of integer numbers $\mathbb{Z}$ is a proper subset of the set of real numbers $\mathbb{C}$. The set of real numbers is uncountable but integers are countable, i.e., uncountability is not inherited by $\mathbb{Z}$. Another example is that $\mathbb{N}$ is a recursive set, however there subsets of $\mathbb{N}$ which are not recursive. Also, the set of strings over $0$ and $1$, $(0+1)^*$ is regular but the language $\{0^p \mid p \text{ is prime } \}$ is not regular.

Nevertheless, any subset of $\mathbb{N}$ is countable and hence the countability is inherited.

As for your question "how can a proper subset not inherit the global properties of its parent set", in some particular cases you may be able to explain it by giving mathematical explanation. But in general, i.e., for any set and its proper subset, I think it is just because the nature works that way.

$\endgroup$
  • 1
    $\begingroup$ The mathematical notion you're looking for is called absoluteness: en.wikipedia.org/wiki/Absoluteness The simplest example is that existential properties are upwards absolute and conversely existential properties are downwards absolute, but it gets more interesting than this. $\endgroup$ – Kris Oct 12 '17 at 12:43
  • $\begingroup$ @Kris: Was one of your "existential"s meant to be a "universal"? $\endgroup$ – psmears Oct 12 '17 at 16:50
  • $\begingroup$ Yes, the second 'existential' should read 'universal'. $\endgroup$ – Kris Oct 12 '17 at 20:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.