Share Your Experience: Take the 2024 Developer Survey

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

• 2,516
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