Skip to main content
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 "...
Nathan Davis's user avatar
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.'s user avatar
  • 161k
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 ...
Arno's user avatar
  • 3,183
13 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,...
Hendrik Jan's user avatar
  • 30.8k
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 ...
Yuval Filmus's user avatar
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 \...
Yuval Filmus's user avatar
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$ ...
Yuval Filmus's user avatar
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 ...
adrianN's user avatar
  • 5,951
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, ...
Yuval Filmus's user avatar
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 ...
Aristu's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
8 votes

Notation in NFA, DFA diagrams and language

You need to distinguish between three kinds of operations: Operations on numbers such as 0 and 1. $0^3 = 0$ when $0$ is taken to be a number. Here, $0^3 = 0 ⋅ 0 ⋅ 0$, where $⋅$ is integer ...
reinierpost's user avatar
  • 5,738
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$....
Yuval Filmus's user avatar
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 $...
Tom van der Zanden's user avatar
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.'s user avatar
  • 161k
7 votes
Accepted

Equivalence between alternative definitions of NP

The definition of $\text{NP}$ in terms of verification can be formally stated as follows: A language $L$ is in $\text{NP}$ if there exists a polynomial verifier for $L$ such that for every $x$: $$...
hengxin's user avatar
  • 9,561
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 ...
Yuval Filmus's user avatar
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 ...
fade2black's user avatar
  • 9,837
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 ...
user6530's user avatar
  • 954
6 votes
Accepted

Understanding why ALL_nfa is in co-nspace

To show that $ALL_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$. The complement is $$\overline{ALL_{\...
Hans Hüttel's user avatar
  • 2,516
6 votes

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 ...
Ryan O'Donnell's user avatar
6 votes
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 ...
David Richerby's user avatar
6 votes
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 ...
fade2black's user avatar
  • 9,837
6 votes

How does a nondeterministic Turing machine work?

The difference between deterministic and non-deterministic Turing machines lies in the transition function. In deterministic Turing machines $\delta$ the transition function is a partial function: $\...
user1868607's user avatar
  • 2,194
6 votes

What is difference between nondeterministic polynomial time and exponential time?

Every nondeterministic polynomial time algorithm can be converted to an exponential time algorithm, where exponential means $O(e^{n^C})$ for some constant $C$. The converse probably doesn't hold.
Yuval Filmus's user avatar
6 votes
Accepted

Minimal number of states for an NFA of all different words

Here is a matching $\Omega(k^2)$ lower bound. Consider any NFA for your language. Let $Q_i$ be the set of states $q$ such that: There is some word $w$ of length $i$ such that the NFA could be at ...
Yuval Filmus's user avatar
6 votes

Notation in NFA, DFA diagrams and language

Consider a finite nonempty alphabet $\Sigma$. The set $\Sigma^* = \bigcup\limits_{n\geq 0 } \Sigma^n$ is the set of finite words over $\Sigma$, indeed, for all $n\geq 0$, we define $\Sigma^n$ as the ...
Bader Abu Radi's user avatar
5 votes
Accepted

How are games like chess provably harder than NP?

The fault lies in this statement: So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to ...
D.W.'s user avatar
  • 161k

Only top scored, non community-wiki answers of a minimum length are eligible