Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata)

The above hint did not help me :(

share|cite|improve this question
Are you sure that you've stated this correctly? $L\setminus R$ should be context-free, but it need not be regular. – Brian M. Scott May 8 '12 at 3:13
Thanks, Brian, my mistake – marcos May 8 '12 at 3:25
Phew! Good, it makes sense now. Can you show the second part? It's easier than the first. – Brian M. Scott May 8 '12 at 3:27
up vote 2 down vote accepted

The harder part is showing that $L\setminus R$ is always context-free. The hint actually is useful, once you figure out what to do with it. Let me point you in the right direction by talking about a simpler situation. Suppose that you have finite-state automata $M_1$ and $M_2$ for two regular languages, with state sets $S_1$ and $S_2$, respectively. Make a new FSA $M$ whose state set is $S_1\times S_2$; in $M$ there will be a transition from a state $\langle s_1,s_2\rangle$ to $\langle s_1',s_2'\rangle$ on input $\alpha$ iff $M_1$ has a transition $s_1\stackrel{\alpha}\longrightarrow s_1'$ and $M_2$ has a transition $s_2\stackrel{\alpha}\longrightarrow s_2'$. In essence, $M$ runs $M_1$ and $M_2$ simultaneously on the same input. That makes it easy to adjust the acceptor states of $M$ so that accepts exactly those words that are accepted by $M_1$ but not by $M_2$; I'll leave the details for you to think about. (You'll also have to figure out what the initial state should be, but that's very easy once you get the idea of how $M$ works.) Then you just have to modify the idea so that one of the automata is a pushdown automaton.

The second part is much easier. Two hints:

  • If $\Sigma$ is the alphabet, is $\Sigma^*$ a regular language?
  • Is the class of context-free languages closed under complementation?
share|cite|improve this answer
Cool, I think I got the 1st part: <Ln,Rn> will be accepting on the combined automaton, only if Ln is accepting on the original automaton and Rn is not. – marcos May 8 '12 at 4:39
@mpm: That's right. This trick of making one automaton do the work of two is pretty useful. – Brian M. Scott May 8 '12 at 4:43

Hints: express $R-L$ more basically in set-theoretic terms. Notice anything about what you get in terms of things you know about CFLs? Try some very simple $R$ (always a good tactic, at least to start).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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