Theorem 8.4.6: the unrestricted phrase structure languages are closed under union, concatenation, Kleene closure, positive closure, substitution, and intersection.
Theorem 8.4.7: if language L is total Turing-recognizable, then ¬L is also total Turing-recognizable.
Theorem 8.4.8: if both language L and its complement ¬L are (partial) Turing-recognizable languages, then L (and hence ¬L) is total Turing-recognizable.
Theorem 8.4.4: each phrase structure language is the homomorphic image of the intersection of (deterministic) context-free languages.
Previous slide | Next slide | Back to first slide | View graphic version |