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

274 questions
Filter by
Sorted by
Tagged with
1answer
57 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 ...
1answer
64 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 ...
2answers
190 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(|...
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 ...
1answer
198 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 ...
1answer
233 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 ...
1answer
5k 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 ...
2answers
1k 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 ...
1answer
64 views

1answer
107 views

### Prove: if $\delta_D(q0, w) = p$ then $\delta_N(q0, w) = {p}$

In my textbook, it presents the theorem, "A language L is accepted by some DFA if and only if l is accepted by some NFA". My textbook explains that the "if" portion of the proof is given by the subset ...
3answers
334 views

1answer
365 views

### Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time

This question is taken from an exam of a Computer Theory Course. Describe how a NON-Deterministic Turing Machine with two tapes recognize in linear time palindrome strings with even length that ...
1answer
881 views

### Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?

I'm currently reading the book Introduction to the Theory of Computation (2nd or 3rd Ed.) by Michael Sipser, and have stumbled upon a question in Chapter 1 - Regular Languages, namely when the author ...
2answers
296 views

0answers
38 views

### Is it possible, at least in theory, to “lockfree-ize” algorithms algorithmically?

The problem emerged from a practical case, but thinking on it resulted more and more theoretical directions. Typically, the lock-free algorithms do relative simple things in the practice, but their ...