Editing Context-free grammar (section)

== Undecidable problems ==
Some questions that are undecidable for wider classes of grammars become decidable for context-free grammars; e.g. the [[emptiness problem]] (whether the grammar generates any terminal strings at all), is undecidable for [[context-sensitive grammar]]s, but decidable for context-free grammars.

However, many problems are [[Undecidable problem|undecidable]] even for context-free grammars; the most prominent ones are handled in the following.

=== Universality ===
Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?{{sfn|Sipser|1997|loc=Theorem 5.10|p=181}}{{sfn|Hopcroft|Ullman|1979|p=281}}

A reduction can be demonstrated to this problem from the well-known undecidable problem of determining whether a [[Turing machine]] accepts a particular input (the [[halting problem]]). The reduction uses the concept of a ''[[computation history]]'', a string describing an entire computation of a [[Turing machine]]. A CFG can be constructed that generates all strings that are not accepting computation histories for a particular Turing machine on a particular input, and thus it will accept all strings only if the machine does not accept that input.

=== Language equality ===
Given two CFGs, do they generate the same language?{{sfn|Hopcroft|Ullman|1979|p=281}}<ref name="eom"/>

The undecidability of this problem is a direct consequence of the previous: it is impossible to even decide whether a CFG is equivalent to the trivial CFG defining the language of all strings.

=== Language inclusion ===
Given two CFGs, can the first one generate all strings that the second one can generate?{{sfn|Hopcroft|Ullman|1979|p=281}}<ref name="eom"/>

If this problem was decidable, then language equality could be decided too: two CFGs <math>G_1</math> and <math>G_2</math> generate the same language if <math>L(G_1)</math> is a subset of <math>L(G_2)</math> and <math>L(G_2)</math> is a subset of <math>L(G_1)</math>.

=== Being in a lower or higher level of the Chomsky hierarchy ===
Using [[Greibach's theorem]], it can be shown that the two following problems are undecidable:
* Given a [[context-sensitive grammar]], does it describe a context-free language?
* Given a context-free grammar, does it describe a [[regular language]]?{{sfn|Hopcroft|Ullman|1979|p=281}}<ref name="eom">{{citation|title=Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia"|first=Michiel|last=Hazewinkel|publisher=Springer|year=1994|isbn=978-1-55608-003-6|at=Vol. IV, p. 56|url=https://books.google.com/books?id=s9F71NJxwzoC&pg=PA56}}.</ref>

=== Grammar ambiguity ===
Given a CFG, is it [[Ambiguous grammar|ambiguous]]?

The undecidability of this problem follows from the fact that if an algorithm to determine ambiguity existed, the [[Post correspondence problem]] could be decided, which is known to be undecidable.{{sfn|Hopcroft|Ullman|1979|loc=Theorem 8.9|pp=200–201}} This may be proved by [[Ogden's lemma#Undecidability|Ogden's lemma]].<ref>{{Cite journal |last=Ogden |first=William |date=September 1968 |title=A helpful result for proving inherent ambiguity |url=http://dx.doi.org/10.1007/bf01694004 |journal=Mathematical Systems Theory |volume=2 |issue=3 |pages=191–194 |doi=10.1007/bf01694004 |s2cid=13197551 |issn=0025-5661}}  Here: p.4</ref>

=== Language disjointness ===
Given two CFGs, is there any string derivable from both grammars?

If this problem was decidable, the undecidable [[Post correspondence problem]] (PCP) could be decided, too: given strings <math>\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N</math> over some alphabet <math>\{a_1, \ldots, a_k\}</math>, let the grammar {{tmath|G_1}} consist of the rule
:<math>S \to \alpha_1 S \beta_1^{rev} | \cdots | \alpha_N S \beta_N^{rev} | b</math>;
where <math>\beta_i^{rev}</math> denotes the [[String (computer science)#Reversal|reversed]] string <math>\beta_i</math> and <math>b</math> does not occur among the <math>a_i</math>; and let grammar {{tmath|G_2}} consist of  the rule
:<math>T \to a_1 T a_1^{rev} | \cdots | a_k T a_k^{rev} | b</math>;
Then the PCP instance given by <math>\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N</math> has a solution if and only if {{tmath|L(G_1)}} and {{tmath|L(G_2)}} share a derivable string. The left of the string (before the <math> b </math>) will represent the top of the solution for the PCP instance while the right side will be the bottom in reverse.