How to Make Arbitrary Grammars Look Like Context-Free Grammars

DOI10.1137/0202014zbMath0298.68057OpenAlexW1990211242MaRDI QIDQ4053130

Walter J. Savitch

Publication date: 1973

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0202014

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Cancellation in context-free languages: enrichment by reduction ⋮ Parsimonious computational completeness ⋮ On the generating power of regularly controlled bidirectional grammars ⋮ Normal forms for phrase-structure grammars ⋮ Unnamed Item ⋮ Monadic Thue systems ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ On non context-free grammar forms ⋮ On inverse deterministic pushdown transductions ⋮ On characterizations of recursively enumerable languages ⋮ The ancestor width of grammars and languages ⋮ Homogeneous grammars with a reduced number of non-context-free products