6
$\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$
3

2 Answers 2

Reset to default
7
$\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$
2
  • $\begingroup$ so is my assumption about both a and b correct? that they both are necessarily context-free? $\endgroup$
    – Kudayar Pirimbaev
    May 11, 2013 at 9:44
  • $\begingroup$ @KudayarPirimbaev yes, but you didn't need that $N$ is also a DCFL. $\endgroup$
    – Luke Mathieson
    May 11, 2013 at 9:57
5
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .