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
4
votes
1
answer
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, ...
- 141
0
votes
0
answers
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 ...
- 1
0
votes
0
answers
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 ...
- 233
1
vote
0
answers
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 ...
- 11
0
votes
0
answers
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 ...
- 315
0
votes
0
answers
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 ...
- 315
0
votes
1
answer
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 ...
0
votes
1
answer
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 ...
- 51
1
vote
1
answer
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,...
- 115
2
votes
0
answers
46
views
Proving the language 2-SIMPLE-PATH is in NL
The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c}
\mathsf{there\;are\;two\;different}\\
\mathsf{simple\;paths\;from}\;s\;\...
- 145
1
vote
1
answer
135
views
What is the smallest NFA you can design for {a^n : n =/= 1003}
What is the smallest NFA that could be design for a^n where n!=1003?
I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
- 25
0
votes
0
answers
43
views
Is there any way to tell which states are final states in a finite state automata given only its grammar?
Problem
In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
3
votes
1
answer
986
views
When converting a epsilon NFA to NFA to DFA, how to handle the start state?
Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3
We know when converting from epsilon NFA to NFA, we apply the following formula for ...
- 305
0
votes
1
answer
323
views
Conversion of epsilon NFA to DFA, handling epsilon transitions
I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs"
Case 0: Michael Sipser asks us to handle ...
- 305
1
vote
1
answer
217
views
Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states
Let's say we have a NFA as follows:
It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon
My question is do we take epsilon transition ...
- 305
0
votes
1
answer
196
views
Confusion regarding the intuition behind epsilon transition in NFA
I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )
Let's use this E-NFA as an example
My question is, do we ...
- 305
0
votes
1
answer
259
views
When converting from nfa to dfa, do we always ignore the trap state?
Let's say we have a NFA such as follows:
We know it's equivalent DFA is follows, after minimization:
We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of ...
- 305
2
votes
0
answers
72
views
constructing non-trivial graph with known shortest Hamiltonian path
I'm interested in testing some Traveling Salesperson (TSP) greedy approximation algorithms for finding the shortest Hamiltonian path for very large graphs. Assume I can construct whatever graph I ...
- 121
0
votes
0
answers
36
views
Is it correct to describe a process as "nondeterministic" if it's input isn't necessarily identical?
This question isn't about the code below; however, I am using this as an example. In the below example, the break statement gets executed seemingly randomly when the mouse button is clicked; it's ...
- 101
0
votes
0
answers
23
views
How are we sure choose is going to halt? question regarding a section from Elaine Rich's Automata, Computability and Complexity book?
I have a problem regarding the choose algorithm, I provide the algorithm's definition and it's use in the book,I attached a picture for the Illustration and for how the algorithm is used.
choose (x ...
- 11
3
votes
0
answers
42
views
Given a complexity class C for problems which can be solved using exponential time and an exponential number of random bits. C ⊆ NEXP?
There must be a complexity class C that includes exactly the problems that can be solved in exponential time and having access to a truly random coin (which in turns implies that you will be able to ...
- 145
0
votes
2
answers
579
views
DFA and NFA Equivalence Proof
I'm taking a Theory of Computation class and we went over the proof to show that for any NFA there is an equivalent DFA, which I understand the proof fully in this case. But if it were in reverse, for ...
- 1
1
vote
2
answers
87
views
Consequences of the Halting Problem
The halting problem is semi-decidable.
Does that mean that:
If a program terminates it can always be established/determined?
If a program does not terminate
It can sometimes be established/...
- 141
10
votes
4
answers
2k
views
Probabilistic methods for undecidable problem
An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic ...
- 219
0
votes
1
answer
326
views
Meaning of lambda-transitions in npda
It is for me unclear how I can derive from a npda whether the lambda-transition means “I don’t care which symbol I read” or “I have read all the symbols”.
For example, see the following automata:
If ...
- 89
0
votes
0
answers
280
views
Non-deterministic Pushdown Automaton to Context-Free Grammar
While doing the exercise about questions about transforming NPDA to CFG, I encountered the following question:
Find a CFG for the following NPDA $M = (\{q_0, q_1\}, \{a, b\}, \{A, z\}, \delta, q_0, z, ...
- 101
-1
votes
1
answer
58
views
Does a random phenomenon have a pre defined probability distribution? what does it mean for something to be random?
While studying Shannon's notion of perfect secrecy I came upon the idea that a bit is perfectly random if it happens to be 0 or 1 with an equal probability. What does this mean? Also, what can we say ...
- 1
0
votes
0
answers
49
views
Why does "NP is closed under Kleene star" proof reject correct word? [duplicate]
Show that P and NP are closed under Kleene star. I found possible solutions to these problems, more specifically:
P - finding all subwords from a giving word and looking if there is a connection ...
- 1
1
vote
1
answer
216
views
Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$
$L= \{ a^nb^m | n \le m \le 2n \}$
As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to ...
- 155
1
vote
1
answer
121
views
Exact formulation of definition of $NP$, in relation to $R$
One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial ...
- 125
1
vote
1
answer
195
views
A small issue regarding the proof of Savitch's Theorem
Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.
...
- 125
0
votes
0
answers
39
views
Translate det. Turingmachine into formula
in the cook-levin theorem a nondet. Turingmachine is translated into a formula of the form:
$\phi$ = $\phi$$_{1}$ $\land$ $\phi$$_{2}$ $\land$ $\phi$$_{3}$ $\land$ $\phi$$_{4}$. I want to know what ...
- 11
0
votes
1
answer
51
views
Do certain epsilon transitions have to be a part of an epsilon nfa?
Hello,
Im new to learning epsilon nfas, and I have been wondering if we could leave certain epsilon transitions out, and if so would it still be a valid epsilon nfa?
For example regarding the image, ...
- 13
1
vote
2
answers
461
views
NFA to recognize the language ${ab}$
In Michael Sipser's Introduction to the Theory of Computation, Example 1.56 shows how to convert $\left(\text{ab }\cup\text{ a}\right)^*$ to an NFA. It builds up from the smallest subexpression to ...
- 113
1
vote
1
answer
78
views
Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?
An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
- 313
-2
votes
1
answer
72
views
How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?
Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method
I end up with this:
My ...
- 305
2
votes
2
answers
151
views
Is ε a part of alphabet or property of alphabet and NFA in FA
I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following:
3rd point of the above image is the ...
- 305
1
vote
1
answer
88
views
Implications of Savitch's theorem
I'm trying to figure out if the following statements are true:
• Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$.
• Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$.
• ...
- 413
3
votes
1
answer
43
views
Build an automaton from a given automaton to prove regularity of more complex strings
let $L$ be a regular language, and let $A=\{\Sigma, Q, q_0, F, \delta\}$ be a DFA such that $L = L(A)$.
I need to prove that $$L_p=\{xy\in\Sigma^*\mid\delta(q_0, y)=p\text{ and } \delta(p, x)\in F\}$$ ...
- 261
1
vote
1
answer
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$:
<...
- 193
1
vote
1
answer
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$?&...
- 1,106
0
votes
0
answers
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, ...
- 145
0
votes
0
answers
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
1
vote
0
answers
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 ...
- 358
0
votes
0
answers
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.
2
votes
0
answers
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-...
- 272
1
vote
1
answer
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}...
- 123
0
votes
1
answer
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 ...
- 29
1
vote
1
answer
220
views
Describing the language of this Automaton
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. ...
- 111
1
vote
1
answer
42
views
Can distirbuted processing, OS processes or even threads be used to simulate a non deterministic turing machine adequately on small datasets?
For example for the traveling salesman problem which is a proven NP-Complete problem, if we spawn a thread at each node in the graph such that each of those threads will, in turn, spawn as many ...
- 273