Consider the following classes of languages:
(a) Regular, (b) Context-free, (c) The class of the complements of context-free language, (d) Deterministic context-free.
Give a Venn diagram of these classes; that is, represent each class by "bubble", so that inclusions, intersections, etc. of classes are reflected accurately.
I think $(d) \subset (b) \subset \ (a)$ and $(c) \subset (a)$, where (c) has no intersection with (b) and (d).
Is this correct?
On
Every regular language is context-free: you can see this either by noticing that every regular grammar is a context-free grammar, or by realizing that a DFA is just a pushdown automaton (PDA) without a stack, i.e., a special case of a PDA. In fact, a DFA is a deterministic PDA without a stack. Thus, every regular language is deterministic context-free. And as you say, every deterministic context-free language is certainly context-free. Let’s leave (c) alone for a bit and concentrate on (a), (b), and (d).
The language $L_0=\{0^n1^n:n\in\Bbb N\}$ is a well-known example of a context-free language that is not regular, and it’s not hard to verify that $L_0$ is deterministic context-free by constructing a deterministic PDA that accepts it. This shows that (a) is a proper subset of (d). The language $L_1$ of even-length palindromes is context-free but not deterministic context-free, so (d) is a proper subset of (b).
To complete the Venn diagram, we need to determine how (c) overlaps with the other three sets. Regular languages are closed under complementation, and every regular language is context-free, so every regular language is also the complement of a context free language: (a) is a subset of (c). Deterministic context-free languages are also closed under complementation, so every deterministic context-free language is the complement of a context-free language: (d) is also a subset of (c).
However, context-free languages are not closed under complementation, so there are context-free languages that are not the complements of context-free languages, and there are complements of context-free languages that are not context-free: (b) and (c) have non-empty intersection (since both contain (d)), but each contains languages not in the other. All that remains is to check whether (c) contains any context-free languages that are not deterministic context-free, and it does, since the complement of $L_1$ is context-free [PDF]. Thus, we have the following Venn diagram:
Your inclusions are not entirely correct. Every regular language is accepted by a DFA (recall the NFA to DFA procedure). A DFA is a PDA which does not use the stack. So every regular language is a deterministic CFL. Thus, (a) $\subset$ (d). You deduced correctly that (b) $\subset$ (d).
Now CFLs are not closed under either intersection or complementation. However, regular languages are closed under complementation. So (c) intersects non-trivially with (b) and (d).