Arbitrary Grammars Generating Context-Free Languages

摘要

If G is a grammar such that in each noncontext-free rule of G, the right side contains a string of terminals longer than any terminal string appearing between two nonterminals in the left side; then the language generated by G is context-free. Six previous results follow as simple corollaries of this theorem. (Author)