Editing Context-free language (section)

===Decidability===
In formal language theory, questions about regular languages are usually decidable, but ones about context-free languages are often not. It is decidable whether such a language is finite, but not whether it contains every possible string, is regular, is unambiguous, or is equivalent to a language with a different grammar.

The following problems are [[Undecidable problem|undecidable]] for arbitrarily given [[context-free grammar]]s A and B:
*Equivalence: is <math>L(A)=L(B)</math>?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(1)}}
*Disjointness: is <math>L(A) \cap L(B) = \emptyset </math> ?{{sfn|Hopcroft|Ullman|1979|p=202|loc=Theorem 8.10}} However, the intersection of a context-free language and a ''regular'' language is context-free,<ref>{{harvtxt|Salomaa|1973}}, p. 59, Theorem 6.7</ref>{{sfn|Hopcroft|Ullman|1979|p=135|loc=Theorem 6.5}} hence the variant of the problem where ''B'' is a regular grammar is decidable (see "Emptiness" below).
*Containment: is <math>L(A) \subseteq L(B)</math> ?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(2)}} Again, the variant of the problem where ''B'' is a regular grammar is decidable,{{citation needed|date=December 2015}} while that where ''A'' is regular is generally not.{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(4)}}
*Universality: is <math>L(A)=\Sigma^*</math>?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.11}}
*Regularity: is <math>L(A)</math> a regular language?{{sfn|Hopcroft|Ullman|1979|p=205|loc=Theorem 8.15}}
*Ambiguity: is every grammar for <math>L(A)</math> ambiguous?{{sfn|Hopcroft|Ullman|1979|p=206|loc=Theorem 8.16}}

The following problems are ''decidable'' for arbitrary context-free languages:
*Emptiness: Given a context-free grammar ''A'', is <math>L(A) = \emptyset</math> ?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(a)}}
*Finiteness: Given a context-free grammar ''A'', is <math>L(A)</math> finite?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(b)}}
*Membership: Given a context-free grammar ''G'', and  a word <math>w</math>, does <math>w \in L(G)</math> ? Efficient polynomial-time algorithms for the membership problem are the [[CYK algorithm]] and [[Earley parser|Earley's Algorithm]].

According to Hopcroft, Motwani, Ullman (2003),<ref>{{cite book|author1=John E. Hopcroft |author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation| year=2003| publisher=Addison Wesley}} Here: Sect.7.6, p.304, and Sect.9.7, p.411</ref> 
many of the fundamental closure and (un)decidability properties of context-free languages were shown in the 1961 paper of [[Yehoshua Bar-Hillel|Bar-Hillel]], Perles, and Shamir<ref name="Bar-Hillel.Perles.Shamir.1961">{{cite journal|author1=Yehoshua Bar-Hillel |author2=Micha Asher Perles |author3=Eli Shamir | title=On Formal Properties of Simple Phrase-Structure Grammars| journal=Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung| year=1961| volume=14| number=2| pages=143–172}}</ref>