Editing Context-free language (section)

===Closure properties===
The class of context-free languages is [[closure (mathematics)|closed]] under the following operations. That is, if ''L'' and ''P'' are context-free languages, the following languages are context-free as well:
*the [[union (set theory)|union]] <math>L \cup P</math> of ''L'' and ''P''{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
*the reversal of ''L''{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4d}}
*the [[concatenation]] <math>L \cdot P</math> of ''L'' and ''P''{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
*the [[Kleene star]] <math>L^*</math> of ''L''{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
*the image <math>\varphi(L)</math> of ''L'' under a [[String operations#String homomorphism|homomorphism]] <math>\varphi</math>{{sfn|Hopcroft|Ullman|1979|p=131-132|loc=Corollary of Theorem 6.2}}
*the image <math>\varphi^{-1}(L)</math> of ''L'' under an [[String operations#String homomorphism|inverse homomorphism]] <math>\varphi^{-1}</math>{{sfn|Hopcroft|Ullman|1979|p=132|loc=Theorem 6.3}}
*the [[circular shift#Applications|circular shift]] of ''L'' (the language <math>\{vu : uv \in L \}</math>){{sfn|Hopcroft|Ullman|1979|p=142-144|loc=Exercise 6.4c}}
*the prefix closure of ''L'' (the set of all [[Prefix (computer science)|prefix]]es of strings from ''L''){{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4b}}
*the [[Quotient of a formal language|quotient]] ''L''/''R'' of ''L'' by a regular language ''R''{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4a}}

====Nonclosure under intersection, complement, and difference====
The context-free languages are not closed under intersection.  This can be seen by taking the languages <math>A = \{a^n b^n c^m \mid m, n \geq 0 \}</math> and <math>B = \{a^m b^n c^n \mid m,n \geq 0\}</math>, which are both context-free.<ref group=note>A context-free grammar for the language ''A'' is given by the following production rules, taking ''S'' as the start symbol: ''S'' → ''Sc'' | ''aTb'' | ''ε''; ''T'' → ''aTb'' | ''ε''. The grammar for ''B'' is analogous.</ref> Their intersection is <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math>, which can be shown to be non-context-free by the [[pumping lemma for context-free languages]]. As a consequence, context-free languages cannot be closed under complementation, as for any languages ''A'' and ''B'', their intersection can be expressed by union and complement:  <math>A \cap B = \overline{\overline{A} \cup \overline{B}} </math>. In particular, context-free language cannot be closed under difference, since complement can be expressed by difference: <math>\overline{L} = \Sigma^* \setminus L</math>.<ref name="Scheinberg.1960">{{cite journal | url=https://core.ac.uk/download/pdf/82210847.pdf |archive-url=https://web.archive.org/web/20181126005901/https://core.ac.uk/download/pdf/82210847.pdf |archive-date=2018-11-26 |url-status=live | author=Stephen Scheinberg | title=Note on the Boolean Properties of Context Free Languages | journal=Information and Control | volume=3 | pages=372&ndash;375 | year=1960 | issue=4 | doi=10.1016/s0019-9958(60)90965-7| doi-access=free }}</ref>

However, if ''L'' is a context-free language and ''D'' is a regular language then both their intersection <math>L\cap D</math> and their difference <math>L\setminus D</math> are context-free languages.<ref>{{Cite web|last1=Beigel|first1=Richard|last2=Gasarch|first2=William|title=A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's|url=http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf |archive-url=https://web.archive.org/web/20141212060332/http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf |archive-date=2014-12-12 |url-status=live|access-date=June 6, 2020|website=University of Maryland Department of Computer Science}}</ref>