NASA NTRS · 19740041376
Non-context-free grammars generating context-free languages
Abstract
If G is a grammar such that in each non-context-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 corollaries of this theorem.
Keep this discovery
Explore connections, maps & timelines
Baker, B. S.. 1974-03-01. Non-context-free grammars generating context-free languages. https://ntrs.nasa.gov/citations/19740041376
Cite the original work for its findings. Save a collection to share your selection of sources.