# Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

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 :(

-

1
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

## 2 Answers

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?
-

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).

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9468101263046265, "perplexity_flag": "head"}