22
$\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.
Improve this question
$\endgroup$
5
  • 1
    $\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 Dougherty
    Jun 1, 2015 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, 2015 at 12:38
  • 4
    $\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, 2015 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, 2015 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, 2015 at 0:46

3 Answers 3

Reset to default
1
$\begingroup$

A nondeterministic machine leaves choice points open: points at which multiple continuations can be taken.

Two ways to 'determinize' this:

  • backtracking: follow the tree of possibilities in depth-first order
  • GLR: follow all branches at once, in parallel, breadth-first order

The resulting parsers are deterministic; they can be defined as automata. Do they satisfy your request? If not, why not?

Improve this answer
$\endgroup$
0
$\begingroup$

As far as I know, we do not know whether Non- deterministic context-sensitive languages are more powerful than deterministic context-sensitive languages. And the simplest reason behind this is: Till now no-one has been able to give a language that is accepted by the non-deterministic LBA and not accepted by the deterministic LBA. So if someone can come up with one such language that is accepted by ND LBA and not accepted by deterministic LBA then only this will be proven. As we know this method of proving is called proof by contradiction. Because proving something is TRUE is a hard problem but proving something FALSE is easy, just get one instance where it fails and we're done.

Improve this answer
$\endgroup$
-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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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