Problem Detail: Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a push-down automaton) and Type 0 by a state machine with two stacks (or, equivalently, a tape, as is the case for Turing Machines), how do Type 1 languages fit into this picture? And what advantages does it bring to determine that a language is not only Type 0 but Type 1?
Asked By : bitmask
Answered By : Alex ten Brink
The context-sensitive languages are exactly the languages that can be recognized by a Turing machine using linear space and non-determinism. You can simulate such a Turing machine using exponential time, so you can recognize any such language in exponential time. Do note that the problem of recognizing some context-sensitive languages is $PSPACE$-complete, which means we’re pretty sure you can’t do better than exponential time. Comparing this to type 0 languages, this means you can at least say something about how long it takes to recognize the language. A type 0 language may not even be decidable: the language of all Turing machines that halt is a type 0 language, but as recognizing this language is exactly the halting problem, it is not decidable. Context-sensitive grammars are not very useful in practice. Context-free grammars are intuitive to work with, but as the examples on Wikipedia show, context-sensitive grammars very quickly become rather messy. Programs using polynomial space are much more easily designed (and the $PSPACE$-completeness guarantees the existence of some equivalent CSG that is only polynomially larger than the space usage of your algorithm). The reason for their existence is that they form a very natural extension of context-free grammars (you allow context to determine which productions are valid). This will probably have inspired Chomsky to define them and name them the type 1 languages. Remember that this definition was made before computers became as fast as they are today: it’s more of interest to formal language theorists than for programmers. Unrestricted grammars get even weirder: there’s no longer a notion of ‘expanding’ a nonterminal and replacing it with a production, possibly depending on context. You’re allowed to freely modify the context as well. This makes unrestricted grammars even less intuitive to work with: programs are equivalent and a lot more intuitive.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14
