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!
314
questions
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.
...
