24
votes
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 "...
- 622
23
votes
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 ...
D.W.♦
- 156k
19
votes
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,683
13
votes
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 ...
- 275k
12
votes
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 ...
- 81.4k
12
votes
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,807
12
votes
Accepted
Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?
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 \...
- 275k
12
votes
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,...
- 29.8k
11
votes
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$ ...
- 275k
10
votes
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,931
9
votes
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,807
9
votes
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 ...
- 275k
9
votes
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 ...
- 275k
9
votes
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, ...
- 275k
9
votes
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
9
votes
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 ...
- 275k
8
votes
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 ...
- 81.4k
8
votes
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 ...
- 851
8
votes
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 ...
- 275k
7
votes
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$ ...
- 17k
7
votes
Accepted
What complexity class would this version of generalized chess fall?
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.2k
7
votes
Accepted
How do nondeterministic Turing machines compute general function problems?
One accepted definition is as follows: a function $f$ (whose output is at most polynomial in its input) is in the class $\mathsf{FNP}$ if given $x,y$ one can decide in polynomial time whether $f(x)=y$....
- 275k
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 ...
D.W.♦
- 156k
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 ...
- 275k
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,757
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 ...
- 852
6
votes
What real-world computer languages cannot be described by deterministic grammars?
Yes. Many modern programming languages have this property, including Algol 60, C, and C++; see below for details.
Algol 60 famously had the dangling else problem, for some programs, it was ambiguous ...
D.W.♦
- 156k
6
votes
Accepted
Deterministic vs. Non-Deterministic PDA?
Your definition is wrong. A PDA is non-deterministic if in some state there are several possible transitions. It doesn't matter if that applies to a transition to a final state.
Your example is ...
- 13.9k
6
votes
Accepted
How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$
The more classical statement is that if $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \textsf{MA}$, due to Babai, Fortnow and Lund. Impagliazzo, Kabanets and Wigderson showed that $\...
- 275k
Only top scored, non community-wiki answers of a minimum length are eligible