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

### 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 ...
• 3,183
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,...
• 30.8k
Accepted

### Why nondeterminism?

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

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

• 2,516

### How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p_2$

There is a more 'elementary' proof of the problem that doesn't involve the polynomial-encoding/self-correction ideas of BFL. The result appears in the original Karp-Lipton paper and is credited to ...
Accepted

### How do we know for sure that EXPTIME ≠ P?

The time hierarchy theorem says that, for any reasonable function $f$, there are problems that can be decided in time $O(f(n))$ that cannot be decided in time, say, $O(f(n)/n)$. (There are ...
• 81.9k
Accepted

### Why we can't use non-deterministic turing machines in this case?

Your reasoning is not wrong. But recall that decidability requires TM machine halt with YES if $\exists w \text{ such that } w^4 \in L(G)$ or NO if $\nexists w \text{ such that }w^4 \in L(G)$. In ...
• 9,837