When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.
For the first and last levels1 (regular languages and recursively enumerable languages), it makes no difference to the power of the model whether we consider deterministic or nondeterministic machines, i.e. DFAs are equivalent to NFAs, and DTMs are equivalent to NTMs2.
However for PDAs and LBAs, the situation is different. Deterministic PDAs recognise a strictly smaller set of languages than nondeterministic PDAs. It is also a significant open question whether deterministic LBAs are as powerful as nondeterministic LBAs or not .
This prompts my question:
Is there a machine model that characterises the context-free languages, but for which non-determinism adds no extra power? (If not, is there some property of CFLs which suggests a reason for this?)
It seems unlikely (to me) that it would be provable that context-free languages somehow need nondeterminism, but there doesn't seem to be a (known) machine model for which deterministic machines are sufficient.
The extension question is the same, but for context-sensitive languages.
- S.-Y. Kuroda, "Classes of Languages and Linear Bound Automata", Information and Control, 7:207-223, 1964.
- Side question for the comments, is there a reason for the levels (ordered by set inclusion) of the Chomsky hierarchy to be number 3 to 0, instead of 0 to 3?
- To be clear, I'm talking about the languages that can be recognised only. Obviously questions of complexity are radically affected by such a change.