Why is non-determinism useful concept?

Problem Detail: 

An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state.

When we are trying to model real systems, why include nondeterminism in Automata theory?

Asked By : tanmoy

Answered By : Grijesh Chauhan

Yes, you are correct computers are deterministic automate. Non-deterministic models are more useful for theoretical purpose, sometime the deterministic solution is not as obvious to the definition(or say problem statement) and so little hard to find solution. Then one approach is that first design a non-deterministic model that may be comparatively easy to design and then try to convert it into a deterministic one. Below, I have tried to demonstrate what I mean with an example. Consider regular expression:

(01)*01(0 + 1)*   

Now suppose, if you are asked to draw DFA for the language generated by above RE.

With my knowledge of designing FAs, I know that (1) when a * present in regular expression indicated I need corresponding loop in FA (2) concatenate operations like a.b means something like: (q0)─a→(q1)─b→(q2).

So, at my fist attempt I would draw an NFA like:

Thought this is not a deterministic solution but looks very simple FA that can be easily designed using the given regular expression. My kind-of-analogy to show similarity between the above regular expression and my NFA is as below:

1. The loop at state q₀ should be for (01)*
2. 01 (after (01)*) gives (q0)─0→(q1)─1→(q2)
3. (0 + 1)* gives a self loop at state q₂ for label 0, 1

According to my analogy I think the FA I drawn above is comparatively simple to draw from given RE. And luckily in class of finite automata every Non-deterministic model can be converted into an equivalent deterministic one. We have algorithmic method to convert an NFA into DFA. So I can easily convert above NFA into a DFA:

Other part is unfortunately this is not always possible to convert a non-deterministic model into deterministic one, for example class for deterministic push down automate is subset of class of deterministic push-down automate "check venn diagram" and you can't always convert an NPDA into a PDA.

Usually when it is not possible to convert a non-deterministic solution into deterministic one then with the help of non-deterministic solution we define deterministic solution in sub-domain (or say partial domain) instead of complete domain. Or we define solution in some other ways (e.g. greedy approach) that of-course may not give you an optimal solution.

Sometimes non-determinism is an effective mechanism for describing some complicated problem/solution precisely and effectively, for an example non-deterministic machines can serve as model of search-and-backtrack algorithm (read: How string process in non-deterministic model using backtrack). Oppositely deterministic models better represents efficient, minimized and less-redundant solutions.

Here I would also like to quote from Wikipedia Use of Nondeterministic algorithm:

In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.

A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P vs NP.

As @keshlam also mentioned in his comment: "Nondeterminism" is in practice used to refer to any unpredictability in the outcome of some process. For an example, Concurrent programs exhibit non-deterministic behaviour - two executions of the same program with the same input can produce different results (if concurrency control mechanism are not applied ). Read more about this in "Usefulness Of Non Determinism".

I would also suggest you to read following links:
1. What is the difference between non-determinism and randomness?
2. 9.2.2 Nondeterministic vs. Probabilistic Models: (a). Nondeterministic: I have no idea what nature will do. (b). Probabilistic: I have been observing nature and gathering statistics.
3. Nondeterministic programming

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22472