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

What is the difference between deterministic and confluent?

I understand deterministic as a function for some input will always give the same output, and these inputs and outputs can be sets of values represent by a predicate. I understand confluent as ...
1
vote
1answer
57 views

Explaining NFA in words

I have an NFA, and the question I am asked is : Let π‘Ž < 𝑏 < 𝑐. Now in simple English, express the language of the NFA to explain what type of strings are accepted by it. In simple English, my ...
0
votes
1answer
45 views

Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$

I have been working on the following homework question, and I just can't seem to make any progress: Construct a finite automaton having fewer than 36 states that recognizes the language $\{s \in a^* :...
1
vote
2answers
37 views

Constructing a NFA from a regular expression

I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression. I started by constructing the NFA ...
1
vote
1answer
34 views

Constructing a NFA that accept complement of language L of another NFA

if given a language $L$ recognized by NFA $N_0$ over an alphabet $\Sigma$. Is it possible to find a general way of constructing an NFA $N_1$ that accept $L^C$ such that $L^C= \{w \in \Sigma^{*} |\mid ...
0
votes
1answer
35 views

new language accepted by FA when new transitions are added to a FA?

found this question online and I am trying to solve this question. I have solved this question but I think I might be missing some cases. Could someone verify if my answers are correct? Let N = (Ξ£ βˆͺ {...
4
votes
0answers
34 views

Simultaneous reachability of NFA states

Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$. I am interested for ...
2
votes
1answer
55 views

this language and acceptance by queue automaton

I don't know how to prove or show that: $ L_1 = \{xx|x \in \Sigma^\ast\} $ (that can be accepted by queue automaton) If it would be possible, show by deterministic queue automaton, if not, by non-...
1
vote
1answer
26 views

PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1

Consider the language $\{ uv : \text{$|u| \ge |v|$ and $v$ contains a 1}\}$. I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if ...
1
vote
1answer
69 views

Conversion of $\epsilon$-NFA to a DFA

So, I was watching a video about the conversion of $\epsilon$-NFA to a DFA. In the resulted DFA, she didn't write the state 4 in any successor set of the sets containing the state 3, and her ...
-1
votes
2answers
89 views

Find language and regular expression

I don't know how to find the Language and the regular expression for each one. there are any special method for those kind of question?
1
vote
1answer
107 views

Building non-deterministic automata

I'm trying to make non deterministic automata for specific language . I cant understand my mistake! Rules: 1){a,b,c} 2) if I have the sequence "bb" and later in the word I have the sequence &...
0
votes
1answer
120 views

Is NP in NP/Poly?

The answer is yes, NP/poly is defined as the class of problems solvable in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function--the advice ...
0
votes
1answer
40 views

What is the relationship between the number of transition rules for an NDTM and the resulting number of computational branches?

How can an NDTM have a growing number of branches as you feed larger and larger inputs with only finite number of transition rules specified--ie what is the relationship between the number of branches ...
0
votes
0answers
23 views

How to explain that a program that runs in NTIME(O(lg n)) is in the class P?

if a non-deterministic program executes only lg(n) decisions on each branch of the computation tree, then the problem this program solves is in P? That means, there is a deterministic algorithm that ...
0
votes
0answers
42 views

Why does converting a NDTM to a a DTM result in a higher time complexity?

I feel like I am really close to understanding the difference between P vs NP, and I think it comes down to this. The confusion stems from the fact that both P and NP problems are done in polynomial ...
1
vote
1answer
53 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | Ο΅ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
0
votes
0answers
25 views

Is there a decision problem in NP whose corresponding function problem is not in #P?

I am trying to get an imagination of the class #P for my bachelor thesis. Right now I think of it as a DTM that runs every possible path to run an algorithm on some decision problem at once. But in ...
0
votes
0answers
62 views

How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language: $$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$ is undecidable? I looked at the proof for $A_{TM}$ ...
0
votes
0answers
77 views

NFA recognizing strings in $\{0,1\}^*$ that have two zeros separated $4i$ characters, for some $i\geq1$

I am trying to design a nondeterministic finite automaton that recognizes the language of strings in $ \{0,1\}^{\ast}$ that have two zeros separated by a string of length 4i, for some $i \geq 1$. Let $...
0
votes
0answers
90 views

Generalization of automaton - Sipser example 1.33

I am trying to construct a nfa that generalizes Example 1.33 found in the book Introduction to the Theory of Computation by Sipser, but I am quite sure that my transition function is wrong. I'd like ...
1
vote
2answers
57 views

How are useless states created NFA to DFA

So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA ...
4
votes
1answer
175 views

Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_aβˆ’|u|_b\le5\}$ is regular

I try to show that this language is regular: $L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_aβˆ’|u|_b\le5\}$ If I build a NFA and run on it every substring of w (skip other letters ...
0
votes
1answer
100 views

Is it incorrect too say that this function problem cannot be in $FNP$?

Decision Problem: Is $2^k$ + $M$ NOT a prime? $K$ and $M$ are our inputs represented as integers. Function Variant: Output the result of $2^k$ + $m$ We can consider, $M$ = $0$. Proof that calculating ...
-1
votes
1answer
81 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
16 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 ...
1
vote
1answer
65 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 ...
0
votes
1answer
27 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 ...
2
votes
1answer
40 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
141 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
32 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. ...
1
vote
1answer
22 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
1answer
52 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 ...
2
votes
1answer
114 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
39 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
56 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
83 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
3answers
202 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
34 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
2answers
215 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 ...
3
votes
1answer
203 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
1answer
53 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
votes
1answer
107 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
86 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?
1
vote
1answer
79 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$, ...
1
vote
1answer
65 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
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
344 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 ...
2
votes
1answer
84 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 =...
2
votes
1answer
85 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
2 3 4 5
…
7