Theorem 8.4.1: for each Turing acceptor T there exists a phrase structure grammar G so that L(T) = L(G).
Theorem 8.4.2: for each unrestricted phrase structure grammar G there exists a Turing machine T so that L(G) = L(T).
Corollary 8.4.3: each context-sensitive language is total Turing-recognizable.
Previous slide | Next slide | Back to first slide | View graphic version |