# 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
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 ...
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 ...
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(|...
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 ...
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 ...
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 ...
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 ...
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 ...
64 views

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 ...
334 views

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 ...
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 ...