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
1
vote
1answer
84 views

NTM's and the halting problem

It is often stated that nondeterministic Turing machines cannot recognize any more languages than ordinary Turing machines. In particular, it is stated that there is no NTM that can take as input a ...
2
votes
1answer
801 views

STCON is NL complete - but why is the reduction in L?

I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity I understand the reduction, but how is it logspace? I understand each state is of $O(\log(n))$ space....
1
vote
1answer
245 views

Is a non-deterministic turing machine that both accepts and rejects the same input valid?

I.e. - if a TM accepts the word 0011100 on one path, while on another the same word is rejected. Do we say that 0011100 is part of the language, or do we say that it is not a valid TM?
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 ...
0
votes
0answers
74 views

Generating a Covering Array Matrix with Simulated Annealing

I've been reading the following paper to understand how I can develop a non deterministic algorithm for test cases generation https://www.researchgate.net/publication/293043297_A_two-...
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"?...
0
votes
1answer
52 views

Show that checking if there exists word not containg patterns from list is in $PSPACE$

There are given: alphabet $Σ$ with some symbols $a,b$. list of forbidden patterns Result: Is there exists word of form $a\Sigma^*b$ such that it doesn't contains (as subword) ...
2
votes
1answer
533 views

Prove that $L$ is closed under Kleene star iff $L=NL$

Prove that $L$ is closed under Kleene star iff $L=NL$ Hi, I am trying to solve this exercise, but it is quiet difficult. Of course first part is very easy: Let assume that $L=NL$. Lets consider ...
2
votes
1answer
837 views

Question about NP problem certificates and P=NP

From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate. My ...
0
votes
0answers
19 views

A recognizing “unique” words [duplicate]

By unique words we understand the such word $w$ that every character in the word occur at most once, for example: $\Sigma = \{a,b,c\}$ $w = abc$, $v = abca$ $w$ is unique, $v$ is not. Now, we have a ...
2
votes
2answers
3k views

NFA-epsilon: epsilon loops, and how do I deal with them?

I am currently studying Automatons and have one, albeit simple, question about NFA-epsilon 'loops' I know that a string can advance using epsilon without having anything read. So my first question ...
3
votes
1answer
378 views

Why we can't use non-deterministic turing machines in this case?

Can you explain me why we can't show decidability of problem using non-determinism ? I know that this problem (described below) is not decidability, however I can't understand why following reasoning ...
5
votes
2answers
743 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 ...
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. ...
2
votes
1answer
353 views

single tape NTM to single tape DTM equivalence

I am having some trouble understanding the equivalence of DTM's and NTM's. If you have Sipser its under 7.11; where he says that any NTM $N$ that halts after $t(n)$ steps has an equivalent DTM $D$ ...
3
votes
1answer
371 views

Understanding of SPACE in non deterministic Turing Machines

Let's consider the following situation. We have a finitie alphabet $A$. Let $A = \{a_1, .., a_k\}$ We consider words over $A$ of length exactly $n$. I am trying to solve some problem and I am going to:...
3
votes
1answer
49 views

Mapping many transition functions into two transition functions

Continuing from this answer: https://cs.stackexchange.com/a/56072/43035 I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two ...
5
votes
1answer
170 views

Space-unconstructable function in the proof of Savitch's theorem

I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it. The proof I'm talking about is the same as is currently on ...
1
vote
1answer
266 views

Non-deterministic logarithmic time complexity class

Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$? It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to ...
2
votes
3answers
643 views

Equivalence between alternative definitions of NP

I'm having some problems in understanding the two alternative definitions of NP. They're presented as equivalent, but to me they seem to define different class of problems. Intuitively, we can think ...
2
votes
1answer
820 views

Time Complexity OF NTM vs TM

In Sipser, It is given Pg. 284 Let t(n) be a function, where t(n) ≥ n. Then every t(n) time non-deterministic single-tape Turing machine has an equivalent 2 O(t(n)) time deterministic single ...
2
votes
1answer
35 views

Can Nondet Rabin Tree automaton be determinized?

In other words, are they equally powerful? (for word automata the answer is "yes"; this question is about tree automata). (i am talking about tree automata that work on $in$finite trees)
2
votes
1answer
216 views

When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar?

Options given were: (a) 2 (b) 3 (c) 4 (d) 5 This question was a part of my assignment. I think the answer is 2 internal states - one start state and the other end state/acceptance state, but ...
-1
votes
1answer
1k views

Product construction for given two finite automata

I need to construct a finite automata which accept a language $L = L_1 \cap L_2$, where $L_1$ and $L_2$ are given below. $L_1 = \{ w \mid w $ is divisible by 2 } $L_1 = \{ w \mid w $ is ...
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 ...
3
votes
2answers
260 views

Puzzle/game of NP class for a high school student

Is there any puzzle or game which cannot be decided in polynomial time and whose problem description can be easily understood by a kid? If it is a fun puzzle so much the better. I want to demonstrate ...
0
votes
1answer
43 views

Bogo sort on NDTM

As we know on NDTM all the possible solutions for a given problem is verified the similar kind of work is done in bogo sort sequentially. So in future if an NDTM will be there. can we say it will be ...
1
vote
0answers
22 views

Why can't a server provide guaranteed service with only bounded nondeterminsm?

The wikipedia page Actor Model and Process Calculi History, presents the following claim: The semantics [of CSP] provided bounded nondeterminism unlike the Actor model with unbounded nondeterminism....
0
votes
0answers
128 views

Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$

I have a question: Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$. I can answer no for DFA for below language and its minimal DFA that has 4 final states . $...
1
vote
1answer
48 views

Is it possible to turn an eulerian NFA into a linear size DFA?

In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states. But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n ...
5
votes
2answers
596 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 ...
1
vote
0answers
22 views

Will computers always behave in an expected way, given constant electrical input? [closed]

For the purposes of this question, please forget about computers being unable to perform as expected due to excess workloads, exceeded capacities, or general bad hardware/devious software (e.g. a ...
0
votes
1answer
47 views

What can be said about the given language?

$L = \left \{ ab^{n}a^{n}|n>0 \right \} \bigcup \left \{ aab^ka^{2k} | k>0 \right \}$ What can be said about the given language L ? According to me, I think it is CFL and not DCFL as I tried ...
1
vote
1answer
473 views

relation between ntime and dtime

Given DTIME($n^2$) contains NTIME($n^{100}$) show that P=NP. I think it's supposed to be straightforward but I just can't see it. Take $L$, a language in NP. $L$ has a Turing machine which runs in ...
4
votes
1answer
324 views

Using Brzozowski's derivatives method to construct a minimal DFA

so I am currently learning about dfa and nfa and i came across the following question which requires me to use Brzozowski's derivatives method to construct a minimal DFA recognizing the language ...
4
votes
1answer
149 views

deterministic finite automaton for “does contain substring $w$” is of linear size

A (non-deterministic) finite state automaton for "all strings that contain substring $w$" is very simple. Just make the path for $w$ and add looped transitions for all letters at the first initial ...
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 ...
5
votes
1answer
133 views

Resulting complexity class for allowing two passes over witness in NL?

I know that when an NL Turing machine is allowed to go back and forth freely, the resulting class of problems solvable on it is NP. But limit of two passes over the witness tape, does not seem to add ...
0
votes
0answers
194 views

graph has at most 2017 connected components is in NL

I need to show that deciding whether a graph G has at most 2017 strongly connected components in in NL. After searching, i found a previous answer: Checking whether a digraph on $n$ vertices ...
0
votes
0answers
100 views

Reduce Nondeterminism in Pushdown Automata

I know there might be some situations where we want transitions to be only taken when the stack is empty, and transitions to be taken only when the input stream is empty. We can create an additional ...
2
votes
1answer
217 views

Understanding why ALL_nfa is in co-nspace

I'm trying to understand Sipser's example showing that $ALL_{nfa} \in Co-NSPACE(n)$, where $$ALL_{nfa} = \{ <A> | A \text{ is an NFA such that } L(A) = \Sigma^*\}.$$ The algorithm can be seen ...
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". ​ ...
1
vote
1answer
425 views

Is the given language DCFL?

$a^ib^jc^k | (i = j)$ then k is even? I can write it as $a^ib^ic^k$ where k is even OR $a^ib^jc^k where (i != j)$ Both are DCFL and union of DCFL may be DCFL, but I think because of OR operator it ...
0
votes
0answers
23 views

Can there exist a smaller NFA then a minimal DFA [duplicate]

So every NFA can be transformed to a DFA and every DFA can be transformed to a minimal DFA. But every NFA can also be transformed to a GNFA (generalized NFA) with 2 states. This is just the start and ...
4
votes
0answers
607 views

Which programming languages have a syntax that can be described by deterministic context-free grammars?

This question asks which programming languages have a syntax that cannot be described by deterministic context-free grammars - the answer is "Many [...] including Algol 60, C, and C++". Until ...
1
vote
1answer
563 views

How to minimize the following DFA?

Consider the DFA, M=({1, 2, 3, 4, 5, 6}, {a, b}, 1, {2, 5}, δ), whose δ is specified below. I calculated the following and got unmarked states (5,2) and (6,3) (6,3) looks okay but there is something ...
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 ...
2
votes
2answers
1k views

Size comparison of NFA and minimal DFA [duplicate]

Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? ...
7
votes
2answers
475 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. ...
3
votes
2answers
458 views

How are games like chess provably harder than NP?

From this question, I had the debate about how problems harder than NP are proved. I said that intuitively I understand it as (from this video explaining that some problems are provably harder than ...