Editing Context-free grammar (section)

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