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!
336
questions
0
votes
2answers
45 views
Show that {xy : x ∈ {a}*, y ∈ {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
59 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
70 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
28 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
59 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
105 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
57 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
48 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
46 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
76 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
53 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
58 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
49 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
97 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
76 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
161 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
132 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
321 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
19 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
119 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
20 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
51 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
35 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
62 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
293 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
83 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
38 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
55 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
70 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
64 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
116 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
116 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
128 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
160 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
43 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
110 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
92 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
124 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
108 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
93 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
188 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 ...
1
vote
1answer
102 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
151 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
18 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
92 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
28 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 ...