# Tag Info

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

18

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

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 $... 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 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 ... 10 You can show that$\mathsf{NL} \subseteq \mathsf{NL}$as follows. We are given an$\mathsf{NL}$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 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 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 ... 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 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$... 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 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 You can prove the lower bound on the number of states using Myhill-Nerode theory. Suppose that we are given a language$L$, in this case the language over$\{0,1\}$of words in which the$n$th last symbol is$1$. We say that two words$x,y$(over the same alphabet) are equivalent if for all words$z$,$xz \in L$iff$yz \in L$. It is easy to check that if ... 7 It can be hard to grasp why we can just reason about an NTM to prove the Kleene star closure for decidable languages. The important fact is that any nondeterministic TM can be simulated by a deterministic TM. In some cases, it will just take a whole lot of time. When the topic is decidable languages, we are only concerned with whether something can be ... 7 Just like any automaton, a PDA is nondeterministic if (and only if) the transition relation is not a function, that is there are configurations that have multiple possible succeeding configurations. If this is the case for reachable configurations, this means that a non-deterministic automaton has inputs for which there are multiple computations. Here, the ... 7 NFAs might be used in practice, check out this answer on stackexchange. The reason is that the powerset construction can be simulated on-the-fly, so to speak. In order to simulate an NFA on a deterministic computer, we just keep track of the possible states that the NFA could be in. Typically, this number would be small, and so the simulation would be fast. ... 7 This is a problematic question. There is a way to check equivalence of automata, which I'll now explain, but I'm afraid it won't help you, as you will see at the end. Recall that two sets$A$and$B$are equal iff$A\subseteq B$and$B\subseteq A$(this is the definition of set equality). Thus, it is enough for you to verify that$L(D)\subseteq L(N)$and$L(...

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