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
37 views

Is this push-down automaton non-deterministic, as JFLAP states?

There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism. In this example it is detecting non-determinism in state ...
1
vote
2answers
67 views

Conversion of nfa with self-loop to one without self-loop

For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the ...
0
votes
1answer
35 views

How is the NP verifier polynomial?

If we start with the definition of L being in NP if "there exists a polynomial NTM that decides L" (where polynomial for an NTM means the length of the worst run as a function of the size/length of ...
-1
votes
1answer
20 views

Formal definition of non deterministic PDA

How would you convert the following formal definition of deterministic pushdown automata into non deterministic ? Deterministic PDAs In general terms, a deterministic PDA is one in which there is at ...
0
votes
0answers
13 views

Nondeterministic Turing Machine for $L^*$

If $T$ is a Turing Machine that accept a language $L$, I want to define a Turing Machine $T'$ such that accepts the language $L^*$. An approach: $T'$ is a nondeterministic Turing Machine which has ...
0
votes
1answer
25 views

Can an $NDTM$ simultaneously perform a set of operations on all strings of a given length?

Can an $NDTM$ perform a set of operations on all strings of a given length $b$, at the same time? Aka can it operate on all strings of a given length by doing something like: spawn $2^b$ branches then ...
1
vote
2answers
1k views

Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions

I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk ...
2
votes
1answer
33 views

Is s-grammar powerful enough to generate all possible DCFL?

In s-grammar all productions are in form of A → 𝑎𝛼 , A∈V , a∈T , 𝛼∈V* "... and any pair (A, a) occurs at most once in P." [P. Linz, 6th ed. , p. 144] s-...
0
votes
2answers
127 views

Can a non-deterministic machine merge its branches?

Does an NDTM have the power to combine computational branches ie. can a result from branch A be used in the next step in the computation along branch B? Can branches use each others' results, ...
-1
votes
1answer
29 views

Can enumeration take advantage of non-determinism?

If I want to build an NDTM to enumerate a list (of all Turing machines, for example) is there a way to use non-determinism to "speed this up" or take advantage of it somehow? What types of of r.e. ...
32
votes
7answers
11k views

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
1
vote
1answer
14 views

Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have $$ NSPACE(S(n)) \subseteq DSPACE(S(n)^2) $$ Am wondering, what happens if $S(n)$ is fully time-...
0
votes
2answers
181 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 ...
2
votes
1answer
59 views

When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
2
votes
1answer
21 views

State complexity of converting epsilon-NFAs to NFAs without epsilon transitions

I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$. Is there a ...
1
vote
1answer
53 views

If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?

Suppose, I wanted to verify the solution to $2$^$3$. Which is $8$. The $powers~of~2$ have only one 1-bit at the start of the binary-string. Verify Solution Efficently ...
1
vote
0answers
79 views

Question about proof of Lemma 2.41 - Sipser book

Doesn't the modification described in paragraph three potentially introduce non-determinism? For example, say neither a, b, x, nor y is the empty string (denoted e). If in the original machine P we ...
1
vote
1answer
52 views

What is $f(n)$ in $NTIME(n)\subseteq DTIME(f(n))$ if $CIRCUITSAT$ is in $P$?

If $CIRCUITSAT$ in $n$ variables and $m$ gates has an $O((nm)^c)$ algorithm for a fixed $c>0$ then $NTIME(n)\subseteq DTIME(O(f(n)))$ for large enough $f(n)$. What is the smallest $f(n)$ in $NTIME(...
0
votes
2answers
74 views

In a NPDA if the stack is empty, where the start/end state are the same can you go again

Thoughts I am wondering if you get a string that goes through the NPDA and arrives back at q0 can I go through the NPDA again so that the last number in the string is not fixed, or is it that once I ...
4
votes
2answers
382 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 ...
0
votes
1answer
33 views

Non Deterministic Turing Machine

Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?
0
votes
1answer
2k 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 ...
3
votes
1answer
97 views

Arden's Rule, DFA & NFA to regular expressions

I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state: if x = s + xr then x = sr*, with $s,r\in$ Regular ...
1
vote
3answers
350 views

NFA for all strings not containing 1010

if I want to design a NFA (that's NOT A DFA) that accepts the set of all strings that do not contain the substring 1010, is this correct? because I can just accept 1010 by capturing it in the starting ...
5
votes
2answers
131 views

motivation and idea of defining non-deterministic Turing machine

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ...
1
vote
1answer
42 views

Is $L \subset 1NL$ when $L \neq NL$? [closed]

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
1
vote
2answers
2k 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 ...
-1
votes
1answer
88 views

Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$

The language is defined as $$L = \{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do ...
-1
votes
2answers
79 views

Why is nondeterminism physically not realizable?

Why it is so hard to make a nondeterministic computer? If such a device is physically realizable then would that be a counterexample to the extended Church-Turing thesis?
4
votes
4answers
523 views

Relaxing the stack in a push down automata

Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol ...
0
votes
0answers
55 views

apply the method of conditional expectations

For a Randomized vertex cover problem Why there is not much hope of deriving an efficient, deterministic version using the method of conditional expectation? I can assume the problem is not ...
0
votes
0answers
21 views

Problem in NP: $EQ1 = \{(p_1,…,p_n): \exists x_1,…,x_m\in Z \ p_1(x_1,…,x_m)=…=p_n(x_1,…,x_m)=0. \}$

I have to following problem to show is in NP class. $EQ1 = \{(p_1,...,p_n): \exists x_1,...,x_m\in Z \ p_1(x_1,...,x_m)=...=p_n(x_1,...,x_m)=0. \}$ Here $p_1,...,p_n$ are polynomials in m variables ...
5
votes
1answer
160 views

If NP is a subset of DTIME[n^O(log n)] then what happens?

If $\mathsf{NP}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$ then what happens? Does it imply $\mathsf{NP}\neq \mathsf{EXP}$? Is there any other consequences such as $\mathsf{BPP}\neq \mathsf{EXP}$? Does ...
2
votes
1answer
62 views

Converting non-deterministic algorithm to deterministic

I was thinking about an non-deterministic algorithm to generate all the subsets of the $\{1..n\}$ set. ...
1
vote
1answer
34 views

Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$

Show if L is in NP, then also L1 is in NP $$L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$$ I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, ...
0
votes
0answers
18 views

Proving a problem is NP [duplicate]

I've seen in many textbooks if say we have a problem $Q$, we write a non-deterministic algorithm in polynomial time to solve problem $Q$, and then from that point it results that $Q\in NP$. Why is ...
2
votes
1answer
211 views

How to prove Shortest Common Superstring is NP-Hard

After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting ...
0
votes
0answers
16 views

Push Down Automatas: Is it still an accept state if stack is not empty?

I'm currently seeing if a PDA is in an accept state give an input string. After reading the entire input tape, I am currently in the accept state. However, in the stack, there are two items in it. So ...
2
votes
1answer
79 views

If A and B are NP-complete, then A ∪ B need not be NP-complete

I am studying the proof of this exercise (link) There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example: $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$ $B =...
0
votes
1answer
355 views

How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
-3
votes
2answers
903 views

Why it is said that LBA is a non deterministic Turing Machine

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
4
votes
1answer
351 views

How to determine if a language is deterministic context-free language?

I have the following question to solve : DCFL means Deterministic Context-Free Language. Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $f(...
12
votes
3answers
543 views

Why nondeterminism?

Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
3
votes
0answers
47 views

Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language? This question is based on a recent question regarding ...
0
votes
0answers
70 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 ...
2
votes
1answer
74 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
285 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$: $δ(...
4
votes
1answer
160 views

Upper bounds for $NP$ based on $NEXP = EXP$

It's open whether $EXP = NEXP \to P = NP$ (the other direction can be shown by padding). My question: has there been any progress along these lines at all? For example, can we show that $EXP = NEXP \...
0
votes
1answer
54 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 ...
6
votes
1answer
56 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.

1
2 3 4 5 6