I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are closed under union, intersection and complement. Now, why are deterministic context free languages not closed under intersection? (the intersection of DCFL need not even be in CFL) but intersection of regular tree languages are closed under intersection? (I get why DCFL union is not in DCFL -- because there is ambiguity).
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The intuition is that the strings of a context-free language are formed by the "frontier" (the leaves) of the derivation trees. The trees themselves are no longer directly visible.
Thus, the intersection of two tree languages consists of the trees the structure of which belongs to two tree grammars. We must be able to map productions of both grammars onto the same tree. Moreover, the tree is visible, we do not have to guess it.
For the intersection of two context-free languages we need two trees, one for each grammar and we only need the two frontiers to be the same. Hence we can find languages like $\{a^nb^nc^n \mid n\ge 1\}$ which is the intersection of two context-free grammars. The first one has a tree structure that verifies that the $a$'s and $b$'s are equal, while the second grammar checks the $b$'s and $c$'s with another tree structure. Also we need to 'guess' the two trees as we only 'see' their frontiers.
I do not think that determinism is essential in this discussion.
answered Mar 21, 2021 at 22:54