The unsolvability of the equality problem for sentential forms of context-free grammars

摘要

The equivalence problem for nondeterministic e-free generalized machines is known to be undecidable. It is shown here that the equivalence problem for these machines can be reduced to the equality problem of the sentential forms of a particular type of linear context-free grammars with a center-marker. Three results which follow are:o(i)The equality problem for sentential forms of c-finite grammars is unsolvable, and therefore the equality problem for the sentential forms of context-free grammars is unsolvable.(ii)The equality problem for sentential forms of bounded context-free grammars is unsolvable.(iii)The equality problem for OL-languages is unsolvable.