4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so is my assumption about both a and b correct? that they both are necessarily context-free? $\endgroup$ – Kudayar Pirimbaev May 11 '13 at 9:44
  • $\begingroup$ @KudayarPirimbaev yes, but you didn't need that $N$ is also a DCFL. $\endgroup$ – Luke Mathieson May 11 '13 at 9:57
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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