3
$\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 ?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
9
$\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.

Improve this answer
$\endgroup$
6
$\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.

Improve this answer
$\endgroup$
3
  • 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, 2017 at 12:43
  • $\begingroup$ @Kris: Was one of your "existential"s meant to be a "universal"? $\endgroup$
    – psmears
    Oct 12, 2017 at 16:50
  • $\begingroup$ Yes, the second 'existential' should read 'universal'. $\endgroup$
    – Kris
    Oct 12, 2017 at 20:12
1
$\begingroup$

DCFL is subset of CFL. But with this we can't say all operations which are closed for CFL are also closed for DCFL. I will give you example :

Suppose we have 2 DCFL whose Union is CFL but not DCFL. When we are considering Union from CFL, product of union is inside CFL. But when we are considering DCFL ,product after Union is not inside DCFL.
I hope problem solved.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Example for union: $\{a^n b^n \colon n \ge 0\}$ and $\{a^n b^{2 n} \colon n \ge 0\}$ $\endgroup$
    – vonbrand
    Feb 7, 2020 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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