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

388 questions
Filter by
Sorted by
Tagged with
65 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, ...
29 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 ...
16 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 ...
1 vote
25 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 ...
56 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 ...
31 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 ...
36 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 ...
55 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 ...
1 vote
461 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,...
46 views

1 vote
104 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$: <...
1 vote
173 views

### Can a nondeterministic Turing machine improve upon a P-time problem?

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$?&...
65 views

### If P = NP then EXP^P = NEXP^NP?

I believe that if P = NP, then that would imply EXP = NEXP (because of the padding argument), and then EXP^P = NEXP^NP (we could replace EXP with NEXP since they are equal, and replace P with NP, ...
211 views

### How to convert a null state transition in nfa to dfa

i am looking to convert regular expression 0* 1* to deterministic finite automaton (DFA) I have tried creating the NFA for the regular expression as given in the above image, From the regular ...
1 vote
131 views

### Confused about the concept of deciding in nondeterministic Turing machines

I read this discussion before. However i’m still confused. I used to think a language decided by a NTM if for every input $w$ in $\Sigma^*$, all of the branches in computation tree leads to a halting ...
25 views

### If a problem is Cook-reducible to a problem in NEXP, is it in NEXP too?

I get why that would be true for EXP but cannot extend the argument to NEXP.
44 views

### Definition of nondeterministic transition system in Principles of Model Checking

In Sec 2.1 of Principles of Model Checking, by Christel Baier and Joost-Pieter Katoen, the authors talk about what constitutes a deterministic transition system (T.S.), and mention two kinds - action-...
1 vote
41 views

### How can I know if more non-determinism can be used in an NFA?

I have to give the transition diagram of an NFA accepting all strings that are not empty and start and end with the same symbol, I should also use non-determinism as much as possible (language is {0,1}...
124 views

### How to simulate an NTM using a DTM?

I've seen questions about how an NTM could simulate a DTM and this seems pretty straightforward to me. However, my text book says you can also simulate an NTM using a DTM. How would this work? I'm ...
1 vote
I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. ...