# Tag Info

## Hot answers tagged nondeterminism

### Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?

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 "...
• 632
Accepted

### Why NFA is called Non-deterministic?

"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 ...
• 141k
Accepted

• 270k
Accepted

### How does the NFA decide in a state where there are multiple equally valid "next states"?

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 ...
• 80.2k
Accepted

### Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?

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,...
• 27.6k
Accepted

### Are DCFLs closed under reversal?

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 ...
• 19.1k
Accepted

### Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

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 ...
• 5,322
Accepted

### How can I show that the Cook-Levin theorem does not relativize?

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 ...
• 4,747
Accepted

### Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?

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 ...
• 5,900
Accepted

### $\mathsf{NL}$ versus $\mathsf{NL}[2]$

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$ ...
• 270k

### How is a nondeterminisitic automaton running on an input?

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 ...
• 111
Accepted

### Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

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 ...
• 270k
Accepted

### Can we show that non-determinism adds no power, for some specific running time?

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 ...
• 270k

### How does a nondeterministic Turing machine work?

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, ...
• 270k

### Why NFA is called Non-deterministic?

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 ...
• 1,483
Accepted

### Non-deterministic Finite Automata | Sipser Example 1.16

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 ...
• 270k
Accepted

### If the universe were predetermined, would non-deterministic automata still make sense?

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

### If the universe were predetermined, would non-deterministic automata still make sense?

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 ...
• 80.2k
Accepted

### Why is simulation by non deterministic Turing machine faster than a deterministic one?

First of all, simulation of non-deterministic universal TM is better than simulation of deterministic universal TM only time-wise. But number of parallel executing threads is very high. In parallel ...
• 4,747

### Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?

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 ...
• 270k
Accepted

### How do I verify that a DFA is equivalent to a NFA?

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$ ...
• 16.2k