MAPPINGS WHICH PRESERVE CONTEXT SENSITIVE LANGUAGES.
Abstract
A basic result which gives a condition under which a (possibly length-decreasing) homomorphism preserves a context sensitive language is presented. Using this result, conditions under which pushdown transducers and linear bounded transducers preserve context sensitive languages are given. The basic result is also applied to show that certain rewriting systems generate context sensitive languages instead of arbitrary recursively enumerable sets. Of special interest is the result that if each rule in a rewriting system has a terminal letter of its right side, then the language generated is context free. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 27, 1965
- Accession Number
- AD0629309
Entities
People
- Seymour Ginsburg
- Sheila A. Greibach
Organizations
- System Development Corporation