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!
261
questions
0
votes
0answers
44 views
Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?
I found en excercise asking this question.
I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic ...
0
votes
0answers
17 views
Is there a universal Turing machine for non-deterministic Turing machines? [on hold]
I'm studying Formal Languages and Automata Theory and I found this question. I'm not sure of knowing the answer, so I'm asking for your help.
I know that a universal Turing machine can emulate any ...
2
votes
1answer
46 views
Like transitive reduction, but removing vertices rather than edges?
Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
1
vote
1answer
33 views
How to make Turing machine deterministic?
My Turing machine starts with an empty tape. It writes a random word of the set $0^n1^n$ to the tape. Hopefully i made no mistakes.
My question is about the productions coming out of state $q_0$:
$δ(...
6
votes
1answer
47 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.
0
votes
1answer
26 views
TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?
So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$ $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The ...
0
votes
1answer
27 views
Why does NTM need to derive certificate to prove “If a language is in in NP iff it is decidable by some nondeterministic polynomial time TM”?
(Sipser's Chapter 7: Time COmplexity, Pgs 294-295)
If we have to prove the forward direction, then we must have the certificate along with the verifier. I don't get why we are "guessing the ...
1
vote
2answers
47 views
Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?
In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
2
votes
2answers
32 views
Given an non-deterministic finite automaton, will its determinization always have unreachable states?
Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states.
If it does, why?
1
vote
0answers
15 views
How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?
For reference, the version of the nondeterministic time hierarchy theorem in question is this one:
The relevant portion of the proof in question (also from Arora-Barak) is here:
Arora-Barak define a ...
2
votes
1answer
33 views
NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}
Consider the following decision problems:
$CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components}
$E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected ...
1
vote
1answer
68 views
Is the halting problem solvable for NPDAs?
After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my ...
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 ...
2
votes
0answers
73 views
Detecting loops in NPDAs
I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
3
votes
2answers
51 views
In what sense are dataflow architectures non-deterministic?
The Wikipedia article mentions non-determinism in the context of dataflow architectures. Arthur Veen's paper mentions non-determinism when it elaborates on MERGE nodes as conditional constructs.
Are ...
2
votes
1answer
31 views
Why “Choice Points” introduce non-determinism in a program?
I'm studying the didactic programming language Oz, following the book "Concepts, Techniques, and Models of Computer Programming".
In the book, the nondeterminism is introduced through the concept of ...
0
votes
1answer
118 views
What's the purpose of the non-deterministic Turing machine?
(*) Acronyms
NTDM := non-deterministic Turing machine.
TM := deterministic Turing machine.
(*) Consider the following idea
The NTDM is able to follow, in parallel, all paths of the tree of the ...
1
vote
2answers
81 views
Describe in words how a NTM can simulate a DTM
I have this assignment
Describe in words how a DTM can simulate a NTM
Describe in wordshow a NTM can simulate a DTM
I'm working on this request and I'm crushing with the comparison.
1-I ...
1
vote
0answers
33 views
Characterization of NFA whose equivalent (minimal) DFA has exponential number of states
(I don't know if there are standard names for this, so) Let's say that a Nondeterministic Finite Automaton (NFA) is $n$-expansive if it has $n$ states and any Deterministic Finite Automaton (DFA) ...
0
votes
0answers
49 views
Proving the Complement of a DCFL is DCFL [duplicate]
If I Have a DCFL $L$ ( a CFL which can be recognised by a DPDA ),
How do I prove that $\overline{L}$ is also a DCFL
I checked my textbook for a proof but I wasn't able to understand the language.
Can ...
3
votes
1answer
70 views
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens? Does it imply $NP\neq EXP$? Is there any other consequences such as $BPP\neq EXP$? Does it also give $PSPACE\subseteq DTIME[n^{O(\log n)}]$?
2
votes
2answers
85 views
Why cannot we enumerate all Turing machines that have no fixed point?
The language
$$
L_1 = \{w \in \{0, 1\}^\ast \mid \exists x \in \{0, 1\}^\ast\colon M_w(x) = x\}
$$
($w$ is an encoding of a DTM, $M_w$ is the respective DTM.)
is not decidable, according to Rice's ...
7
votes
0answers
82 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 ...
1
vote
1answer
80 views
How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?
I currently have a problem with the following question:
Let $L = \{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \}$.
Construct an NTM (non-deterministic Turing ...
5
votes
1answer
104 views
The definition of weakest precondition for a non-deterministic language
In the classical IMP language, the definition of weakest precondition is:
definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"
This is stating that from state s, after ...
3
votes
1answer
130 views
The Law of Excluded Miracle in the language of guarded commands
The definition of weakest precondition is familiar (let me use Isabelle's syntax here):
definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"
the weakest precondition ...
1
vote
2answers
319 views
What to do with empty set during NFA to DFA conversion?
I am currently converting this NFA to a DFA
I have come up with the following DFA:
...
1
vote
2answers
56 views
Understanding Hamiltonian Path, NP vs Co-NP
I am having difficulty understanding the distinction between NP and Co-NP.
According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language: HAMPATH = { (G,s,t) | G is a ...
1
vote
1answer
470 views
PDA of the language where the number of a's are NOT equal to the number of b's
I have this NPDA for language L = {w: num_a(w) == num_b(w)}
all loops in q1
...
0
votes
1answer
55 views
Given a NP Algorithm for SAT, do we expect to have Correct and Incorrect Solutions?
I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says :
In computational complexity theory, nondeterministic algorithms are ones that, ...
3
votes
0answers
35 views
What is the difference between the choice operator and nondeterminism in CSP?
I'm learning CSP now for my research. First time doing formal work in CS. I'm having a hard time understanding the difference between choice $\square$ operator and the nondeterminism $\sqcap$ operator....
2
votes
2answers
324 views
Why SAT Requires A Non-determinstic Algorithm?
I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).
I do understand the difference between a ...
1
vote
1answer
265 views
How to implement a maximal munch lexical analyzer by simulating NFA or running DFA?
I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold ...
1
vote
2answers
468 views
Understanding $\epsilon$ transitions on NFA
I can't understand why $\epsilon$ is accepted. I thought if $\epsilon$ is inputed then it would go from $q_1$ to $q_3$. $a$ is also accepted, but I though if $a$ is inputed then then the NFA would die,...
4
votes
1answer
146 views
How do non-deterministic algorithms work on current machines?
I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia ...
2
votes
1answer
45 views
In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?
In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex ...
0
votes
1answer
115 views
Drawing a NFA for a string
I have these grammar rules defined as follows,
FDL -> FDEF FDL | ε
FDEF -> #feature #: FEXP
FEXP -> #op #( FLIST #)
FLIST -> FEXP #, FEXP | #feature
...
1
vote
1answer
55 views
Can we call deterministic equivalent of all NFA to be finite
Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we ...
1
vote
1answer
46 views
What will happen if input is larger than required in a NFA
This is my first time in the field of TOC so I am not able to provide any self-approach while asking .In the above example what will happen if input string is "1001" or "1111"?The state q4 can be ...
1
vote
2answers
115 views
NP Class Definition of a Certificate
Given the definition for all x ∈ Σ∗
x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1
Lets say the input x = ababab
Then the certificate u shouldn't be longer than p(|x|).
But what would be p(|...
3
votes
1answer
54 views
How to prove existence of the language
Consider such question:
(Prove or disprove) There exists a language in $TIME(2^{n^2})$ that is not in $NTIME(n)$.
I guess that answer is yes because $TIME(2^{n^2})$ and $NTIME(n)$ are totally ...
0
votes
1answer
167 views
Are there any estimated, imperfect or fuzzy sorting algorithms?
I'm implementing some estimation metrics that take samples of optimisation functions and estimate their properties. One of the metrics requires the data to be sorted; however, since the metric is only ...
2
votes
1answer
170 views
Can an algorithm be truly non-deterministic?
I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the ...
3
votes
1answer
4k views
Understanding trap and dead state in automata
Well, this sounds somewhat basic definitions, but I feel they needs to be clearly defined.
In book by Hopcroft et. al., there is an excerpt:
...a dead state, that is, a nonaccepting state that ...
1
vote
2answers
774 views
Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}
The question is in title. Let me repeat:
What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$
I feel both NFA and DFA will take ...
0
votes
1answer
63 views
Is this language NP Hard?
$L=\{$$($$m$,$w$,$n$$)$| $m$ is an encoding of a non-deterministic Turing machine, $w$ is any word/string in the closure of alphabet, i.e. $w\in\Sigma^*$, $n$ is any positive integer, i.e. $n\in\Bbb{Z}...
0
votes
0answers
60 views
Where is proof that palindrom language is nondeterministic? [duplicate]
It is well-known that the language over $T$ with at least 2 symbols is nondeterministic. for simplicity, the language $\{ww^R: w\in\{a,b\}\}$ (even-length palindroms of $a$, $b$) is context-free, but ...
1
vote
2answers
63 views
Do NFAs with $\varepsilon$-moves never terminate?
Suppose in an NFA we have an $\varepsilon$-move from a state $q_0$ to $q_1$. According to Sipser,
Without reading any input, the machine splits into multiple copies one following each of the ...
1
vote
1answer
55 views
Questions on Sipser's NP implying verifiability?
I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up ...
0
votes
1answer
44 views
NFA accepting $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$
I have to construct NFA that accepts language $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$.
My solution is this automata:
Can you tell me, if this is correct or not? If ...
