Are regular languages necessarily deterministic context-free languages?

Question

The original problem

Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers.

a) Is M-N necessarily context-free?

b) Is N-M necessarily context-free?

My attempt

Since DCFLs are closed under complementation, if N is DCFL, then both a and b are true, but are regular languages necessarily DCFLs?

Thanks in advance.

Answer 1

To answer the titular question, yes, all regular languages are deterministic context free languages. For every regular language, there's a DFA, which we can view as a PDA that doesn't use its stack (at least not to do anything useful). Clearly this PDA is deterministic (it's just a DFA).

For the two motivating questions we have (just to make a clear explanation):

1. If $A$ is regular then so is $\overline{A}$.
2. If $B$ is deterministic context free, then so is $\overline{B}$.
3. If $C$ is regular and $D$ is context free, then $C\cap D$ is context free (I'm not sure what happens if $D$ is a DCFL, whether the intersection also is, but it's at least still context free).

Then we have:

a) $M-N = M\cap \overline{N}$, by (1) $\overline{N}$ is regular, by (3) $M\cap \overline{N}$ is context free.

b) $N-M = N\cap\overline{M}$, by (2) $\overline{M}$ is context free (indeed, deterministic), then by (3) $N\cap\overline{M}$ is context free.

So don't actually need that the regular languages are a subset of the deterministic context free languages to answer the questions.

Answer 2

1) Any regular language can be represented by a deterministic finite automaton. Any (deterministic) finite automaton, can be interpreted as a (deterministic) pushdown automata where the stack stays empty. Therefore any regular language is a DCFL.

2) That DCFLs are closed under complement is certainly not enough to justify that the difference of two DCFLs is a DCFL. Since $M-N = M\cap\overline{N}$ you would also need closure under intersection. Unfortunately, DCFLs are not closed under union nor intersection.

Hint: prove that (D)CFLs are closed under intersection with a regular language by considering a (deterministic) PDA for a DCFL, a DFA for some regular language, and building a (deterministic) PDA for the intersection.