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

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


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


13

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


12

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

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.


11

For DFA there is a nice algebraic structure that determines which states can be equivalent, the Myhill-Nerode equivalence on strings is related to minimization of DFA. For NFA the situation is complicated as there is no unique minimal NFA in general. Here is an example for the finite language $\{ ab, ac, bc, ba, ca, cb\}$. The two automata are both state-...


11

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


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

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


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

Here are several ways of thinking about non-determinism (copied from this answer). The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the ...


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


9

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


8

The two terms randomized algorithms and probabilistic algorithms are used in two different contexts. Randomized algorithms are algorithms that use randomness, in contradistinction with deterministic algorithms that do not. Probabilistic algorithms, for example probabilistic algorithms for primality testing, are algorithms that use randomness and could make ...


8

This is elaborated nicely in Dexter Kozen's Theory of Computation textbook, in chapter 2. Savitch's Theorem (Theorem 1 in his paper) says: if $S(n) \ge \log n$, then $\text{NSPACE}(S(n)) \subseteq \text{DSPACE}(S(n)^2)$. Space-constructibility often seems to be assumed in a proof, but this requirement can be removed by restarting the search with a fixed ...


8

You want to know why "the others" obtained a different expression? When contructing a regular expression there is no unique correct answer. There are usually several expressions "that make sense". In this case you use state elimination method (I learned this under the name of Brzozowski and McCluskey). Here the order of removal determines the expression ...


8

Quite simply, the mechanism is magic. The idea of non-determinism is that it simply knows which way it should take in order to accept the word, and it goes that way. If there are multiple ways, it goes one of them. Non-determinism can't be implemented as such in real hardware. We simulate it using techniques such as backtracking. But it's primarily a ...


8

Non-determinism is the same concept in all contexts – the machine is allowed several options to proceed at any given point. However, the semantics are a bit different since DFAs/NFAs and PDAs always define total functions, while Turing machines (deterministic or non-deterministic) in general define partial functions. A partial function is one defined only ...


8

It makes perfect sense. Non-deterministic automata and non-deterministic algorithms in general are useful in many situations. The best known situation is when one designs algorithms (or strategies or recipes or ..) and analyzes them. For example, an algorithm for computing the maximum element of a set of numbers will have a loop of the form "as long as the ...


8

Nondeterministic automata would make perfect sense in a predetermined universe, because, in the sense it is used in computer science, "nondeterministic" does not mean "not predetermined." In particular, the acceptance criterion of nondeterministic machines is defined in terms of the existence of a path of a particular kind through the state transition graph....


8

Please refer Does Cook Levin Theorem relativize?. Also refer to Arora, Implagiazo and Vazirani's paper: Relativizing versus Nonrelativizing Techniques: The Role of local checkability. In the paper by Baker, Gill and Solovay (BGS) on Relativizations of the P =? N P question (SIAM Journal on Computing, 4(4):431–442, December 1975) they give a language $B$ ...


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