A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [nondeterminism]

Questions about automata, formal grammars or other computation-models that specifically relate to the use of nondeterminism. Not to be confused with randomness or ambiguity!

Filter by
Sorted by
Tagged with
31
votes
2answers
7k views

What is the difference between quantum TM and nondetermistic TM?

I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do ...
30
votes
7answers
10k views

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
25
votes
5answers
11k views

What is meant by “solvable by non deterministic algorithm in polynomial time” [duplicate]

In many textbooks NP problems are defined as: Set of all decision problems solvable by non deterministic algorithms in polynomial time I couldn't understand the part "solvable by non deterministic ...
24
votes
3answers
2k views

What are the conditions for a NFA for its equivalent DFA to be maximal in size?

We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
23
votes
10answers
7k views

Why is non-determinism a useful concept?

An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state. When we ...
20
votes
3answers
4k views

How to prove that DFAs from NFAs can have exponential number of states?

All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...
19
votes
4answers
2k views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
15
votes
1answer
1k views

Computational power of deterministic versus nondeterministic min-heap automata

This is a follow-up question of this one. In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: ...
14
votes
7answers
5k views

Why NFA is called Non-deterministic?

I have this [kind of funny] question in mind. Why is the non-deterministic finite automaton called non-deterministic while we define the transitions for inputs. Well, even though there are multiple ...
14
votes
4answers
617 views

Push Down Automatons “guess” - what does that mean?

I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted ...
14
votes
2answers
930 views

Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
14
votes
3answers
6k views

Why is NFA minimization a hard problem when DFA minimization is not?

I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs? I'm not looking for a proof or anything like that--unless a proof is simpler to ...
13
votes
3answers
2k views

Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?

Tomorrow is my presentation and I want to clear my concepts… I've read that in DFA, "For each state, transition on all possible symbols (alphabet) should be defined." Is for each state, defining ...
13
votes
7answers
9k views

Can we say DFA is more efficient than NFA?

I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
12
votes
3answers
21k views

How does an NFA use epsilon transitions?

In the picture below, I'm trying to figure out what exactly this NFA is accepting. What's confusing me is the $\epsilon$ jump at $q_0$. If a $0$ is entered, does the system move to both $q_0$ and $...
10
votes
3answers
2k views

How do I verify that a DFA is equivalent to a NFA?

I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is ...
9
votes
4answers
2k views

Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ...
9
votes
3answers
426 views

Why nondeterminism?

Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
9
votes
1answer
1k views

Non-deterministic Finite Automata | Sipser Example 1.16

I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$. Could someone run ...
9
votes
1answer
2k views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
9
votes
1answer
695 views

Why is this function computable in $O(n^{1.5})$ time?

My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number $i$...
8
votes
4answers
4k views

How does a nondeterministic Turing machine work?

What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"?...
8
votes
3answers
746 views

Why do most scientists believe that P≠NP?

I read that most scientists don't believe that P=NP. It might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some "...
8
votes
1answer
881 views

Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?

I'm currently reading the book Introduction to the Theory of Computation (2nd or 3rd Ed.) by Michael Sipser, and have stumbled upon a question in Chapter 1 - Regular Languages, namely when the author ...
8
votes
1answer
3k views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
8
votes
3answers
386 views

Algorithm to shrink a DFA by introducing nondeterminism?

This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question. I'm doing research where I'm trying to find the structure of complements of a ...
8
votes
2answers
326 views

Why is one often requiring space constructibility in Savitch's theorem?

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
8
votes
1answer
321 views

Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?

These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give ...
8
votes
2answers
889 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
8
votes
2answers
160 views

What is the state of the art in encapsulated search in functional logic programming?

I am particularly interested in solutions to the problem that encapsulated search can depend on the order of evaluation. According to [1], encapsulated search in PAKCS depends on the order of ...
7
votes
4answers
829 views

Are there real lexers that use NFAs directly instead of first transforming them to DFAs?

I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
7
votes
1answer
175 views

Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
7
votes
2answers
476 views

How do nondeterministic Turing machines compute general function problems?

(Hope this hasn't been asked before, but I didn't find anything.) In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. ...
7
votes
2answers
932 views

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

Following is a theorem from Sanjeev Arora and Boaz Barak I am unable to prove : If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p_2$. The previous similar theorem was ...
7
votes
1answer
116 views

$\mathsf{NL}$ versus $\mathsf{NL}[2]$

There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right. ...
7
votes
1answer
1k views

How can I show that the Cook-Levin theorem does not relativize?

The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) : Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not ...
7
votes
1answer
16k views

Converting an NFA to regex using GNFA algorithm?

So I've been trying to crack this for a long time and almost feel like I am going in loops about this question. Given the following NFA: Using the GNFA algorithm get the regular expression. I ...
7
votes
2answers
3k views

Non-deterministic Turing machine that halts on at least one branches of computation

I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing ...
7
votes
1answer
548 views

What real-world computer languages cannot be described by deterministic grammars?

Are there any examples of real-world computer languages that are non-deterministic? By computer languages I include programming languages, markup languages, query languages, modeling language, ...
7
votes
2answers
211 views

Classes of NFAs which allow efficient subset testing or unambiguity conversions

I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete. I'm wondering, ...
7
votes
1answer
225 views

Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

Let $k\in \mathbb N$ I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : |u|=|v|=k\...
7
votes
0answers
83 views

Automata that is Turing complete if you add a nondeterminism

Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
6
votes
1answer
146 views

Are there any known lower-bounds for complexity on Non-determinsitic machines

For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time. Are they any problems where we have known lower bounds for ...
6
votes
1answer
801 views

How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
6
votes
1answer
51 views

What publication first introduced the concept of a non-deterministic Turing machine?

What publication first introduced the concept of a non-deterministic Turing machine? Turing did not define the concept in his 1936 paper.
6
votes
1answer
742 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
6
votes
1answer
265 views

Is there a language with non-isomorphic minimum-state UFAs?

For all regular languages L, by the Myhill-Nerode classes, all state-minimal DFAs for L are isomorphic. ​ On the other hand, "a regular language may have many non-isomorphic state-minimal nfas". ​ ...
6
votes
0answers
200 views

Why does Non Determinism not enhance FA like it does for PDA

Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of ...
5
votes
2answers
597 views

Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?

The wikipedia page Powerset construction says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input". I ...
5
votes
2answers
744 views

Do NPDA work in parallel?

Assume my language is $$ L= ww^{r}\ $$ Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice ...