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 "...
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 ...
user avatar
  • 141k
13 votes
Accepted

How does an NFA use epsilon transitions?

Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states, to simplify this to you: If the string is $\epsilon$ then your automata ends both in $...
user avatar
  • 375
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 ...
user avatar
12 votes

Defining the halting problem for non-deterministic automata

There are a few reasons I think we put less effort into the Halting problem for non-deterministic models. The first is that there are, in fact, two relevant halting problems for a ND model. Given an ...
user avatar
  • 29.1k
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 \...
user avatar
11 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 ...
user avatar
11 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,...
user avatar
  • 27.6k
10 votes
Accepted

Are DCFLs closed under reversal?

I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter. Searching the web does also give a ...
user avatar
  • 19.1k
10 votes
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 ...
user avatar
10 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 ...
user avatar
  • 4,747
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 ...
user avatar
  • 5,900
10 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$ ...
user avatar
9 votes

How is a nondeterminisitic automaton running on an input?

A non-deterministic automaton runs in all possible sequence of states on a given input. It is not a random run. An input symbol is accepted only if in at least one of the runs it has reached an ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
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 ...
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 ...
user avatar
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 ...
user avatar
  • 831
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 ...
user avatar
8 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 ...
user avatar
  • 4,747
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 ...
user avatar
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$ ...
user avatar
  • 16.2k
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 $...
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 ...
user avatar
  • 141k
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 ...
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 ...
user avatar
  • 9,612
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 ...
user avatar
  • 800

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