language defined in BNF is ambiguous, or if two different specifications of a
language are in fact equivalent. But the results that have been established tell us
that this is not possible, and it would be a waste of time to look for an algorithm
for either of these tasks. Keep in mind that this does not rule out the possibility
that there may be ways of getting the answer for specific cases or perhaps even
most interesting ones. What the undecidability results tell us is that there is no
completely general algorithm and that no matter how Many different cases a
method can handle, there are invariably some situations for which it will break
down.
EXERCISES
1. Prove the claim made in Theorem 12.8 that G A and G B by themselves are
unambiguous.
* 2. Show that the problem of determining whether or not
L(G i ) ⊆ L(G 2 )
is undecidable for context-free grammars G 1 ,G 2 .
* 3. Show that for arbitrary context-free grammars G 1 and G 2 , the problem
“L(G 1 ) L (G 2 ) is context-free” is undecidable.
* 4.Show that if the language L (G A ) L(G B ) in Theorem 12.8 is regular, then it
must be empty. Use this to show that the problem “L (G) is regular” is
undecidable for context-free G.
* 5. Let L 1 be a regular language and G a context-free grammar. Show that the
problem “L 1 ⊆ L(G)” is undecidable.
* 6.Let M be any Turing machine. We can assume without loss of generality that
every computation involves an even number of moves. For any such
computation