# Tag Info

### 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 ...
• 148k

### Probabilistic methods for undecidable problem

So, we have a TM $M$ that can in addition flip a fair coin. We have the promise that for every input $M$ will eventually halt and give an answer, no matter what the coin results are. Moreover, we ...
• 2,331
Accepted

• 273k
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.8k
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,787
Accepted

### $\mathsf{NL}$ versus $\mathsf{NL}$

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$ ...
• 273k
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,...
• 28.7k
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

### 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,910
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 ...
• 273k
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 ...
• 273k
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,787

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

### 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 ...
• 273k
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 ...
• 841

### 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.8k

### 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 ...
• 273k
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.6k
Accepted

because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP. It is possible that generalized chess is in $... • 13.1k 7 votes Accepted ### Are there any known lower-bounds for complexity on Non-determinsitic machines No. There are no known polynomial bounds. The best lower bounds known are merely linear. As described here, the situation for circuits at least is "quite depressing": there are no known lower ... • 148k 7 votes ### Do NPDA work in parallel? That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism. The genie. Whenever the machine has a choice, a ... • 273k 7 votes Accepted ### Do NPDA work in parallel? The difference between DPDA and NPDA is that in NPDA there may be more than one possible transition from a single state given input symbol and stack symbol, while in a DPDA there is only one ... • 9,672 7 votes Accepted ### Show$L = ${ w$\in (a,b) ^* $| for every u substring of w,$-5\le|u|_a−|u|_b\le5\}\$ is regular

Nice question! This is a very nontrivial problem involving regular languages. First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to ...
• 835