On the Decidability of Grammar Problems
Harry B. Hunt · Journal of the ACM · 1982
AaSaat^CT The decidability of context-free grammar and language problems in general, especially problems about separabthty and context, grammar and language class membership, and grammatical similarity relauons, is studied.The results are based upon efficient reductions of membership problems for always-halting Turmg machines and the following fundamental property of s-grammars and s-languages:The emptiness-of-intersection problem for pa,rs of s-grammars that generate languages without arbitrarily long common prefixes is decidable but ~s not recorsively time-bounded.