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!
341
questions
1
vote
1answer
41 views
Describing the language of this Automaton
I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. ...
1
vote
1answer
26 views
Can distirbuted processing, OS processes or even threads be used to simulate a non deterministic turing machine adequately on small datasets?
For example for the traveling salesman problem which is a proven NP-Complete problem, if we spawn a thread at each node in the graph such that each of those threads will, in turn, spawn as many ...
3
votes
1answer
81 views
How is the time complexity of a non-deterministic Turing machine defined?
I read different things online about this:
In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n.
So this is only ...
3
votes
1answer
56 views
Is this language $X = \{x:xxx\in L\}$ regular?
I came across this question in my Theory of Computation class recently:
Consider a regular language $L$, and define $X = \{x:xxx\in L\}$. Is this language regular?
I believe that it is regular, and ...
1
vote
1answer
41 views
epsilon-NFA to DFA conversion - What will be the final states and do we need to create empty state in DFA?
Source of this question and problem:
https://www.javatpoint.com/automata-conversion-from-nfa-with-null-to-dfa
This is the question:
So in this figure there are my 1 confusion-:
Don't we need a empty ...
0
votes
2answers
48 views
When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?
The question is-:
THIS is the transition table for NFA-:
Final result as shown in youtube video.
https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49
...
0
votes
1answer
14 views
Problems with simulating NFA with DFA
I have this NFA:
I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when ...
2
votes
1answer
45 views
Are Nondeterministic Finite Automata not allowed 'sink-states'?
By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
0
votes
2answers
76 views
Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language
I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
0
votes
0answers
70 views
My proof for equivalence of DFA and NFA
I came up with this proof for the following theorem:
If $L$ is a language produced by an nfa, then there exists a dfa $M$ where $L(M) = L$.
Is it correct? If it's not, what are the flaws of my proof,...
4
votes
2answers
75 views
Is the language "substrings of a regular language that are over half the length of the superstring" regular?
We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular?
I was provided the ...
0
votes
1answer
32 views
Computation branches on NTM
I would like to run the following string $w=011101$ on the following NTM and figure out the respective computation branches and whether it accepts or rejects that string.
$\text{Start: }(q_0) 011101 $
...
1
vote
2answers
65 views
Can a non-deterministic finite automaton die out before reading the entire string?
I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by:
However, my problem is:
If the ...
1
vote
2answers
116 views
Converting non-deterministic TM to deterministic TM using poly time SAT solver
Suppose there exist deterministic turing machine $M$ that could solve SAT in polynomial time. How can we construct a deterministic TM $N$ ,by using SAT solver $M$, that take as input a non-...
3
votes
1answer
91 views
Showing NP is closed under intersection
I was solving the following question:
Show that $L_1 \cap L_2 \in \mathrm{NP}$ for $L_1,L_2 \in \mathrm{NP}$.
I came a cross this solution on the internet which is:
$M$: On input $w$ —
Run $M_1$ ...
2
votes
1answer
49 views
Number of queries for $NP^{NP}$
So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle
machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(...
2
votes
2answers
68 views
Confused about definition of a non-deterministic decider
Fallowing are some definitions from book "introduction to theory of computation" by sipser.
a nondeterministic turing machine is a decider if all its computation
branches halt on all input.
...
0
votes
1answer
92 views
Counting strongly connected components in a directed graph in $NL$
Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$
I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
3
votes
1answer
56 views
Efficient algorithm to find a rejecting input of an NFA
I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive.
The algorithm ...
1
vote
1answer
59 views
Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
Let $C$ be an uniform complexity class for example $NL$ or $NP$. Is there distinction between $(C/poly)\cap(coC/poly)$ and $(C\cap coC)/poly$?
2
votes
1answer
60 views
Proof that class of languages accepted by DPDA by empty stack is not closed under union
My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property):
$$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d :...
1
vote
1answer
149 views
What does a non-deterministic guess "look like"?
I have been trying to understand the solution to the following problem:
"Show that if $L_2$ and $L_3$ are Turing recognisable, then so is $L_2L_3 = \{w_1w_2 : w_1 \in L_2,w_2\in L_3\}$:
which ...
1
vote
1answer
94 views
Can converting NFA to DFA change the language?
In the context of studying the conversion from an NFA to the equivalent DFA, I came across the following NFA, which accepts all strings over the alphabet $\{0,1\}$ which contain $01$:
After I ...
7
votes
2answers
162 views
Minimal number of states for an NFA of all different words
Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different.
Also, for me $k$ is a known constant. ...
0
votes
2answers
144 views
Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter
I have been trying solve this problem for a while now for a university assignment. I'm required to build a DFA and an NFA for the above question. So far I have been able to solve the DFA but can not ...
0
votes
1answer
32 views
Converting along regular expression to NFA
I have the following regular expression for the set of all strings such that each block of five consecutive symbols contains exactly two 0's (consider the alphabet to be {0, 1}):
(0+1+ϵ)4+(11100+ϵ)r(...
1
vote
2answers
521 views
Regular Expression and NFA: each block of five consecutive symbols contains at least two 0's
Consider the alphabet {0, 1}. How do I find the regular expression for the set of all strings such that each block of five consecutive symbols contains at least two 0's?
Here, by block I mean a given ...
0
votes
0answers
22 views
Are there more succint algorithm for translating NFA's to DFA's?
When translating an NFA to its deterministic equivalent, we get an exponential blowup due to the powerset construction method. I tried to search but couldn't find an appropriate question regarding ...
2
votes
1answer
206 views
Polynomial time verification of Graph Isomorphism problem
Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.
The nondeterministic selection ...
1
vote
0answers
21 views
Constructing an NFA that is equivalent to a regular expression
I am a little stuck at attempting to give an NFA for the regular expression $0^+(10^+0)^∗$
, where the alphabet is ${0, 1}$. I have tried to construct multiple NFA's state diagram and the closest I ...
0
votes
1answer
55 views
Prove no DFA with four states can accept L={111}
Assume we have a language L={111}. Prove no DFA with four states can accept L.
Can’t a DFA with 4 states accept L?
1
vote
1answer
37 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
79 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 ...
1
vote
1answer
71 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
374 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
95 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
42 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
64 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
88 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
77 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
130 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
133 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
137 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
173 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
46 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 ...
1
vote
1answer
104 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
154 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
114 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
115 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
199 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 ...
