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
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 ...
1
vote
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 ...
1
vote
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(|...
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
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 ...
2
votes
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 ...
3
votes
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 ...
1
vote
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 ...
0
votes
1answer
64 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
66 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
70 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
56 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
49 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 ...
0
votes
1answer
466 views

Is every decidable language a deterministic context free language?

I'm trying to get a better understanding for the relationship between decidability and a few other things so that I can get a better grasp of the topic. Any info helps! Is every decidable language a ...
1
vote
3answers
121 views

Is there a method to compress all data without loss (lossless compression)?

I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I ...
0
votes
0answers
109 views

show doubly connected graph is NL complete

The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
5
votes
1answer
176 views

Implications of $NL=P$

What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you
4
votes
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 ...
1
vote
3answers
334 views

Minimal DFA with more states than its equivalent NFA

I understand that using a bad case for subset construction as provided through an example in the book - Introduction to Automata Theory, Languages and Computation, we can definitely have an NFA with $...
4
votes
1answer
167 views

Complement of Mealy machine

How could one reasonably define and construct the complement of a deterministic Mealy machine? My intuition is that the complement should give exactly the opposite of output strings after a specific ...
0
votes
1answer
98 views

Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5

I need to choose a language, design a finite automaton M such that L = L(M). Construct a minimum-state DFA M′ equivalent to M in such a way that the ratio of the number of states in M to the number of ...
9
votes
3answers
425 views

Why nondeterminism?

Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
1
vote
4answers
200 views

How do NFA's make program design any better when converted DFA form can't remember original states?

Here is some content from the book by Peter-Linz I read "Consider a game-playing program where the machine needs to make the decision for the next move [say for tic-tac-toe]. Since there are ...
2
votes
0answers
102 views

Simulating QC using nondeterministic Turing machine

Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine? Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing ...
0
votes
1answer
131 views

Confused b/w non-deterministic finite state automata vs finite state automata

I am reading this example of FSA from book Martin & Jurafsky "Speech and Language Processing". As per definition of FSA you can only transition to one state after consuming one input. In this ...
0
votes
1answer
60 views

If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?

If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971). By the definition of non deterministic ...
0
votes
0answers
37 views

How about boolean formula that is satisfied on every reject path and falsified on every accept path of non deterministic Turing machine? [duplicate]

Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time ...
-1
votes
1answer
87 views

Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)

I read The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971). Cook explains how to create a boolean formula $\Phi$ from $(M,w)$, where $M$ is a non-deterministic Turing machine that ...
1
vote
1answer
127 views

NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?

As a follow-up from my old question here, I'm wondering more about the equivalence proof. Intuitively, NP has been described as the class of all problems which a solution certificate can be verified ...
0
votes
2answers
61 views

Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?

CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form while CNFFAL is the language of all strings that are encoding of falsifiable boolean ...
1
vote
0answers
349 views

Converting a non-deterministic context free grammar to deterministic

I have the non-deterministic context free grammar $$I \to abcX | abdY$$ $$X \to X d | \epsilon$$ $$Y \to XX |I$$ and i want to convert it into a deterministic. I know that the rules $I \to abcX | abdY$...
1
vote
0answers
357 views

Comparing non-deterministic and also the deterministic expressive power of FA, PDA's and TM'S [closed]

I am sorta confused and also could not find a answer online, but in terms of expressive power, . Non-deterministic FA, PDA, TM NFA < NPDA < NTM ...
2
votes
1answer
94 views

On $NP=\Sigma_2^P$ from non-deterministic time?

We know $NP=\bigcup_{k\in\Bbb N}NTIME(n^k)$ and $\Sigma_2^P=NP^{NP}$. Does $\Sigma_2^P\subseteq\bigcup_{k\in\Bbb N}NTIME(n^k)$ also hold (we can do $O(n^k)$ queries to $NP$ oracle which runs in non-...
4
votes
3answers
647 views

What is difference between nondeterministic polynomial time and exponential time?

I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank ...
1
vote
1answer
66 views

Are probabilisitc algorithms deterministic?

I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness? Initially, I thought only ...
0
votes
1answer
72 views

On $UP$, $NP$, $\oplus P$ and $PP$?

We know $UP\subseteq NP\subseteq PP$. Is $UP^{\oplus P}\subseteq NP^{\oplus P}\subseteq PP^{\oplus P}$? I think the first $UP^{\oplus P}\subseteq NP^{\oplus P}$ is straightforward since whatever ...
0
votes
1answer
82 views

Closure of a CFL under specific operation

Consider the following operation on language $L$: $\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$ I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
3
votes
1answer
165 views

Finding non-trivial NFA that accepts all short strings

It is well-known that every non-trivial NFA of $k$ states (an NFA that does not accept all strings) rejects a string of length at most $2^k$. But is this upper bound asymptotically tight ? I found ...
0
votes
1answer
125 views

$U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete

I'm trying to prove $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP-complete. Showing it is NP is trivial. NP-hardness is the hard ...
0
votes
1answer
95 views

Behavior of non-deterministic Turing Machines after $t_i$ seconds

Suppose that I have a non-deterministic Turing Machine $M_1$ and its clone $M_2$. Given a string $x \in \Sigma^*$, it is possible that after $t_i$ seconds $M_1$ accepts $x$ and $M_2$ does not halt ? ...
0
votes
1answer
130 views

What is the deterministic finitite automaton (DFA) for the regex “.*b.”

I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and ...
1
vote
0answers
222 views

Non-deterministic Turing Machine recognizing a context-free Language

This question is taken from an exam of a Computer Theory Course. Describe how a NON-Deterministic Turing Machine with two tapes recognize the language generated from the grammar: $ S \rightarrow SS ...
1
vote
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 ...
8
votes
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 ...
2
votes
2answers
296 views

What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)?

An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that $...
0
votes
0answers
52 views

How are Probability and Non Determinism Related ? Alternatives to handle Non determinism?

I have been thinking about Non-determinism in any kind of state machine. Since I work on machine learning, I tend to think that probability is a means of handling non-determinism. Instead of ...
3
votes
1answer
743 views

Working of NPDA

I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example ...
0
votes
2answers
229 views

Why do the definitions of non-deterministic Turing machines look strange?

I read some definitions of the NDTM in several books. Something makes me confused. Some definitions say that the NDTM $M$ makes an arbitrary choice as to which of its transition functions to apply. ...
2
votes
1answer
163 views

What is the explicit definition about the computablity of non-deterministic Turing machine?

Given a finite alphabet $\Sigma$. We define the set of all words of finite length to be $\Sigma^{*}$. A partial function can become a total function with trivial modifications, thus we just consider ...
3
votes
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 ...