# Tag Info

24

Non-deterministic algorithms are very different from probabilistic algorithms. Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. ...

24

The algorithm you refer to is called the Powerset Construction, and was first published by Michael Rabin and Dana Scott in 1959. To answer your question as stated in the title, there is no maximal DFA for a regular language, since you can always take a DFA and add as many states as you want with transitions between them, but with no transitions between one ...

24

Suppose a DFA was allowed to have missing transitions. What happens if you encounter a symbol which has no transtion defined for it? The result is undefined. That would seem to violate the "deterministic" characteristic of a DFA. However, it's trivial to transform such an incomplete DFA into a complete DFA. Simply add a new state, illegal, and map any ...

23

Adding to Shitikanth's answer, a nondeterministic algorithm is one that has multiple choices in some points during its control flow. The actual choice made when the program runs is not determined by the input or values in registers, or if we are talking about Turing machines, the choice is not determined by the input value and the state; instead an ...

23

"Deterministic" means "if you put the system in the same situation twice, it is guaranteed to make the same choice both times". "Non-deterministic" means "not deterministic", or in other words, "if you put the system in the same situation twice, it might or might not make the same choice both times". A non-deterministic finite automaton (NFA) can have ...

20

As a general preamble, QTMs, TMs and NTMs are all different things (taking huge liberties with a bunch of unspoken assumptions). I'll assume you know what a Turing Machine is. A NTM is a TM where, at any state, with any symbol, the transition function is allowed to have a number of choices of action that is not precisely $1$, i.e. $0$ or more than $1$ (a ...

16

There are two answers, depending on how you define efficient. Compactness of representation Telling more with less: NFAs are more efficient. Converting a DFA to an NFA is straightforward and does not increase the size of the representation. However, there are regular languages for which the smallest DFA is exponentially bigger than the smallest NFA. A ...

16

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 ...

15

An algorithm specifies a method to get from a given input to a desired output that has a certain relation with the input. We say that this algorithm is deterministic if at any point, it is specified exactly and unambiguously what the next step in the algorithm is that must be performed as part of that method, potentially dependent on the input or the partial ...

15

One operation that transforms an NFA into another NFA but does not do so for a DFA is reversal (point all the arrows the other way round, and swap initial states with accepting states). The language recognized by the transformed automaton is the reversed language $L^R = \{u_{n-1}\ldots u_0 \mid u_0\ldots u_{n-1} \in L\}$. Thus one idea is to look for a ...

14

On the meaning of nondeterminism There are two different meanings of 'nondeterminism' at issue here. Quantum mechanics is usually described as being "not deterministic", but the word "nondeterministic" is used in a specialized way in theoretical computer science. One meaning, which applies to quantum mechanics, is just 'not deterministic'. This is usually ...

14

You should be aware that there are two different definitions of nondeterminism being thrown around here. As wikipedia defines it, pretty much "not determinism", that is, any algorithm that doesn't always have the same behavior on the same inputs. Randomized algorithms are a special case of "not deterministic" algorithms, because they fit the definition as I ...

14

In short: non-determinism means to have multiple, equally valid choices of how to continue a computation. Randomisation means to use an external source of (random) bits to guide computation. In order to understand nondeterminism, I suggest you look at finite automata (FA). For a deterministic FA (DFA), the transition function is, well, a function. Given the ...

13

There are a few reasons I think we put less effort into the Halting problem for non-deterministic models. The first is that there are, in fact, two relevant halting problems for a ND model. Given an input $x$ and a non-deterministic machine $M$: Does there exist a valid run of $M$ on $x$ which halts? Does there exist a valid run of $M$ on $x$ which doesn'...

12

An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the ...

12

A DFA is specified by the following data: An alphabet $\Sigma$. A set of states $Q$. An initial state $q_0 \in Q$. A set of final states $F \subseteq Q$. A transition function $\delta\colon Q \times \Sigma \to Q$. As you can see from the signature of $\delta$, it specifies a transition at every state for every symbol.

12

Excellent question! Nondeterminism first appears (so it seems) in a classical paper of Rabin and Scott, Finite automata and their decision problems, in which the authors first describe finite automata as a better abstract model for digital computers than Turing machines, and then define several extensions of the basic model, including nondeterministic finite ...

11

It doesn't decide. Nondeterminism isn't intended to be a realistic model of computation. Check the definition: a nondeterministic automaton accepts if there's any valid sequence of transitions that reach an accepting state.

11

Consider a two state automaton for the language $a^*b$, two transitions from the initial state, one looping with label $a$, the other with label $b$ to the final state. Making the initial state final, would also accept $a^*$.

10

I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter. Searching the web does also give a negative answer, with counter example, on stackoverflow by a member of CS (notation adapted): $(a+b+c)^*WcW^R$, where $W \in (a+b)^+$; this is non-...

10

Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states, to simplify this to you: If the string is $\epsilon$ then your automata ends both in $q_0$ and $q_1$ If your string is '0' it'll be again in $q_0$ and $q_1$ If your string is '1', it'll be only in $q_2$, because if you look from the point of $... 10 The notion of a PDA can be generalized to an$S(n)$auxiliary pushdown automaton ($S(n)$-AuxPDA). It consists of a read-only input tape, surrounded by endmarkers, a finite state control, a read-write storage tape of length$S(n)$, where$n$is the length of the input string, and a stack In "Hopcroft/Ullman (1979) Introduction to Automata Theory, Languages, ... 10 The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000. A DFA doesn't know how much input is left, so the property "the fourth character from the end" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each ... 10 You are confusing$\epsilon$with a letter. It's not a letter! It's just the empty string. Let us consider a slightly more general model, "word-NFA". A word-NFA is like an NFA, but each transition is labeled with an arbitrary word. We say that the word-NFA accepts a word$w$if there is a walk from an initial state to a final state such that if we ... 9 An NP-complete problem can be transformed into another NP-complete problem. There's an abundance of known NP-complete problems, in fact, one could even say that any really interesting problem is NP-complete. So if you know of a way of solving any NP-complete problem$X$quickly, you can take any other NP-complete problem, transform it into an instance of$X$,... 9 It is more the other way around: automata arose first, as mathematical models. And nondeterminism is quite natural, you often have several paths open before you. Instead of some messy way of specifying that all paths must be followed to the end in some order, and perhaps getting bogged down by infinite branches, and... just use nondeterminism. And while ... 9 A non-deterministic automaton runs in all possible sequence of states on a given input. It is not a random run. An input symbol is accepted only if in at least one of the runs it has reached an accepting state after reading the given input. Hope this helps :D 9 If$\mathsf{NTIME}(n^k) \subseteq \mathsf{TIME}(n^\ell)$for any$k,\ell$then$\mathsf{P} = \mathsf{NP}$. Indeed, any problem$L \in \mathsf{NP}$can be solved in non-deterministic time$O(n^r)$for some$r$. Consider now the problem$L' = \{0^{|x|^{r/k}}1x : x \in L\}$. Clearly this problem is still in$\mathsf{NP}$, and furthermore the previous algorithm ... 9 You can show that$\mathsf{NL}[2] \subseteq \mathsf{NL}$as follows. We are given an$\mathsf{NL}[2]$machine$M$, and we want to simulate it with an$\mathsf{NL}$machine$M'$. The first that$M$does is to guess the state$\sigma$of$M'$after it finishes reading the witness tape for the first time. It then simulates two copies of$M$, one starting at$M$'... 9 Take this automaton for instance, it's an NFA and it accepts the string$0110$. To be more pedantic, it accepts strings that end in$10\$. To see that we just need to check whether it reaches an accept state. \begin{align*} q_0 & \rightarrow 1\\ q_0 & \rightarrow 0\\ \color{red}{q_1} &\rightarrow \color{red}{1}\\ q_2 &\rightarrow 0\\ \end{...

Only top voted, non community-wiki answers of a minimum length are eligible