Theorem 7.1.3: each phrase structure language is generated by a context-sensitive grammar augmented with context-free erasing.
Theorem 7.1.4: each phrase structure language is the homomorphic image of an _-free context-sensitive language.
Definition 7.1.3: a homomorphism h: _* ____* is _-free (or non-erasing) if h(_) ° _ for each ___.
Theorem 7.1.5: context-sensitive languages are closed under _ -free homomorphisms.
Previous slide | Next slide | Back to first slide | View graphic version |