19
$\begingroup$

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 [1].

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.

References

  1. S.-Y. Kuroda, "Classes of Languages and Linear Bound Automata", Information and Control, 7:207-223, 1964.

Footnotes

  1. 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?
  2. 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.
$\endgroup$
  • $\begingroup$ So you're asking for the class of languages larger than (but as close as possible) CFLs for which the deterministic version = nondeterministic version? $\endgroup$ – Ryan Jun 1 '15 at 11:25
  • $\begingroup$ @Ryan no, I'm asking if there's a machine model which characterises the CFLs, but for which nondeterministic and deterministic variants are equivalent in power, However assuming there's no positive answer (which I suspect there isn't), that is a good follow up question. $\endgroup$ – Luke Mathieson Jun 1 '15 at 12:38
  • 3
    $\begingroup$ I think the main problem with the question is the lack of a general definition for a "computational model". You could, for example, define a deterministic TM that is equipped with a context-free grammer, that accepts a word iff the grammar generates it. This is a deterministic model that is equivalent to CFL, but it's silly... $\endgroup$ – Shaull Jun 1 '15 at 13:45
  • $\begingroup$ @Shaull, that's a fair point, but it does seem to be hard to give a definition for a "sensible" model. Your example obviously feels unnatural, but I don't think there's a justifiable definitional way around it. $\endgroup$ – Luke Mathieson Jun 1 '15 at 14:02
  • $\begingroup$ To link in Ryan's follow up question, the machine mentioned in Thomas Klimpel's answer (although not as elegant as a PDA), would fit the idea of "natural" in a way that a TM restricted to computing a CFG wouldn't. Maybe the intuition is that a TM with a CFG is explicitly coding in the definition of a CFL, whereas it's not obvious, for example, that CFGs and PDAs should be related, the PDA is a natural extension of DFAs and happens to work for CFLs. $\endgroup$ – Luke Mathieson Jun 2 '15 at 0:46
-2
$\begingroup$

In my understanding of theory of computation, the only situation non-determinism does not give you extra flexibility (i.e,.. power) is at the recursively enumerable/ recursive level. This is primarily because of the halting problem and it's limitations on the TM's capabilities in decidability, which I believe this answers one of your questions in the foot notes as well as a sidebar. The Chomsky Hierarchy is a logical representation of moving up the flexibility latter (if I might say), allowing more power to the machine. Does this help any with your question/thoughts?

As far as the PDA's and LBA's I will have the other accomplished folks here in the community help with that, my experience has been more with TM's and the theory associated with the higher (more RE) part of the hierarchy (at least as taught in my undergrad).

Peter Linz theory of computation

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd_sbs_14_img_0?_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4

$\endgroup$
  • $\begingroup$ This doesn't answer the question. The OP is already aware of what you wrote. $\endgroup$ – Yuval Filmus Dec 18 '16 at 11:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.