# 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!

399 questions
Filter by
Sorted by
Tagged with
1 vote
22 views

### Is the set of languages with verifiers running in polynomial time equal to the set of languages decidable by an NTM running in polynomial time?

I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the ...
134 views

### in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?

in $\epsilon$-NFA (NFAs involving $\epsilon$ transitions) when we have $\epsilon$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every ...
• 353
1 vote
51 views

### Proof that nondeterministic TM runs in exponential time

Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. ...
• 13
35 views

### NFAs that accept a regular language

Just a quick question about regular languages and which NFAs accept them: If I were to draw an NFA that accepts a particular regular language, does that mean the NFA can only accept strings in that ...
698 views

### Notation in NFA, DFA diagrams and language

I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to ...
1 vote
63 views

### Why can't we prove closure under concatenation using DFA?

I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to ...
• 69
1 vote
113 views

### How to construct complement of NFA universality?

Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal? I tried to use the fact that NFA-universality is PSPACE-...
• 123
86 views

### Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$

From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
133 views

### Non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$

I was trying to figure out how can I construct a non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$ I looked at some of the proposed solutions here : Turing ...
• 275
62 views

### How to prove MIP is in NEXP

I was trying to understand the proof of MIP is inside NEXP. I was referring to Rutger's university scribes (link). They define MIP as a class with exponential proof, but that is not the definition I ...
• 243
77 views

### Translating non-deterministic finite automata with counters to deterministic ones

I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, ...
• 141
219 views

### How to convert NFA with multiple start states to NFA with single start state without epsilon transition?

I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition. But I want to know how can I do so without epsilon transition Here's my idea Suppose s1 and ...
• 21
36 views

### Why nondeterministic decider for $HAMPATH$ runs in polynomial time?

( Source: Introduction to the theory of computation, Michael Sipser, 3rd edition ) I know the computation-time of a non-deterministic Turing machine ( NTM ) which is a decider is defined to be the ...
• 233
1 vote
31 views

### Non-Deterministic Turing Machine That Accepts RE-R language

As far as I know for Non-Deterministic Turing Machine (NTM) there are 4 kind of branches: An input is accepted if there is at least one node in the tree that is an accept. An input is rejected if all ...
• 11
192 views

### ALL_{NFA} is PSPACE-complete

Show that $ALL_{NFA}$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^*$} is $\text{PSPACE-complete}$. I've manged to prove that the langauge is in $\text{PSPACE}$. Indeed, it is easy to see ...
• 21
104 views

### Constructing a PDA for $L=${$\exists i,k\in \mathbb{N} : |w|=2k, w_i \neq w_{k+i}$}

I have the main idea, yet I'm uncertain on how to construct this PDA (in terms of states, transitions) We can assume the alphabet $\Sigma$ is {$0,1$}, proving for $\Sigma=${$0,1$} is a sufficient ...
• 355
34 views

### Proving existence of NFA with specific amount of vertices

For every $i$ we define $\Sigma_i=${$1, 2, ..., i$} and a language over said $\Sigma_i$: $L_i=${$w\in \Sigma_i^*| \exists \sigma \in \Sigma_i :\sigma$ does not appear in $w$} And I'm asked to prove ...
• 355
49 views

### Does a non-deterministic Turingmachine reach every possible result?

I have problems to imagine a non-deterministic Turingmachine. Let's make an example: There is the problem of a Vertexcover. Let $G=(V,E)$ be an undirected graph and $k\geq 0$. The question is whether ...
57 views

### Is there a typo in this excerpt from the book?

Michael Sipser's Introduction to Theory of Computation: Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a ...
• 51
1 vote
743 views

### Getting an NFA with only one initial and final state without epsilon transitions

Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions,...
• 115
55 views

• 261
1 vote
125 views

### Use NFA to express the left quotient of the language of a DFA with respect to the language of another DFA

Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*.$ $L_1 \triangleleft L_2 = \{w\in \Sigma^* \mid \exists v\in L_1, vw \in L_2\}$ For clarity, here is python code that shows $L_3 \triangleleft L_4$: <...
• 193
1 vote
Linear search is solvable in O(n) time by a deterministic Turing machine. If we apply a nondeterministic Turing machine to the problem, can we solve the decision problem "Is $x$ in the array $A$?&...