we can then construct the string
This is called a valid computation.
Show that for every M we can construct three context-free grammars G 1 ,
G 2 ,G 3 , such that
(a) the set of all valid computations is L (G 1 ) L (G 2 ), and
(b) the set of all invalid computations (that is, the complement of the set of
valid computations) is L (G 3 ).
Use the results to show that “L(G) = Σ*” is undecidable over the domain of
all context-free grammars G.
* 7. Let G 1 be a context-free grammar and G 2 a regular grammar. Is the problem
L (G 1 ) L (G 2 ) = Ø
decidable?
* 8. Let G 1 and G 2 be grammars with G 1 regular. Is the problem
L (G 1 ) = L (G 2 )
decidable when
(a) G 2 is unrestricted,
(b) when G 2 is context-free,
(c) when G 2 is regular?
12.5 A Question of Efficiency
As long as we are concerned only with computability or decidability, it makes
little difference what model of Turing machine we use. But when we start
looking at possible practical concerns, such as ease of implementation or
This is called a valid computation.
Show that for every M we can construct three context-free grammars G 1 ,
G 2 ,G 3 , such that
(a) the set of all valid computations is L (G 1 ) L (G 2 ), and
(b) the set of all invalid computations (that is, the complement of the set of
valid computations) is L (G 3 ).
Use the results to show that “L(G) = Σ*” is undecidable over the domain of
all context-free grammars G.
* 7. Let G 1 be a context-free grammar and G 2 a regular grammar. Is the problem
L (G 1 ) L (G 2 ) = Ø
decidable?
* 8. Let G 1 and G 2 be grammars with G 1 regular. Is the problem
L (G 1 ) = L (G 2 )
decidable when
(a) G 2 is unrestricted,
(b) when G 2 is context-free,
(c) when G 2 is regular?
12.5 A Question of Efficiency
As long as we are concerned only with computability or decidability, it makes
little difference what model of Turing machine we use. But when we start
looking at possible practical concerns, such as ease of implementation or