If deterministic context-free languages (DCFLs) are not closed under intersection, does this mean that the intersection of two DCFLs will always be context free but may not be deterministic? Or does it mean their intersection may not be context-free?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
The statement itself doesn't imply that. It just means that the intersection of two DCFLs might or might not be a DCFL; and thus presumably could be a DCFL; could be a CFL but not a DCFL; or could be not context-free.
However, we know more actually.
The intersection of two DCFLs could be, of course, a DCFL. For example, you can let both of them be the same DCFL. For another example, just take any two regular languages. Every regular language is a DCFL and the intersection of two regular language is still regular.
Here is an example of two DCFLs the intersection of which is not a CFL. The intersection of $\{a^{n}b^{n}c^m \mid n\ge0, m\ge 0\}$ and $\{a^{n}b^{m}c^m \mid n\ge0, m\ge 0\}$ is the most classical non-CFL, $\{a^{n}b^{n}c^n \mid n\ge0\}$.
Exercise. Find two different non-regular DCFL the intersection of which is a DCFL.
Deeper fact. Given any natural number $n$, there is a language that is the intersection of some $n+1$ DCFLs, but it is not the intersection of any $n$ DCFLs.
