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!
370
questions
-1
votes
0
answers
12
views
CFG to DPDA Conversion explanation?
S → a[S] |S+S| b
I have basically such a grammatik which needs to be converted into DPDA.
I have the solution but I dont really understand how it is being done.Can anyone explain it to me?
S→aQS′R|bR
...
- 1
-1
votes
0
answers
28
views
Is there a non-deterministic polynomial time TM such that $L(M)\in NPC$ and $L(\bar M) \in NPC$?
When $\bar M$ is a non-deterministic polynomial time TM with final states switched: accept to reject and vice versa.
- 1
0
votes
0
answers
41
views
Why does "NP is closed under Kleene star" proof reject correct word? [duplicate]
Show that P and NP are closed under Kleene star. I found possible solutions to these problems, more specifically:
P - finding all subwords from a giving word and looking if there is a connection ...
- 1
1
vote
1
answer
60
views
Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$
$L= \{ a^nb^m | n \le m \le 2n \}$
As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to ...
- 155
1
vote
1
answer
58
views
Exact formulation of definition of $NP$, in relation to $R$
One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial ...
- 133
1
vote
1
answer
143
views
A small issue regarding the proof of Savitch's Theorem
Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.
...
- 133
0
votes
0
answers
31
views
Translate det. Turingmachine into formula
in the cook-levin theorem a nondet. Turingmachine is translated into a formula of the form:
$\phi$ = $\phi$$_{1}$ $\land$ $\phi$$_{2}$ $\land$ $\phi$$_{3}$ $\land$ $\phi$$_{4}$. I want to know what ...
- 11
0
votes
1
answer
27
views
Do certain epsilon transitions have to be a part of an epsilon nfa?
Hello,
Im new to learning epsilon nfas, and I have been wondering if we could leave certain epsilon transitions out, and if so would it still be a valid epsilon nfa?
For example regarding the image, ...
- 13
1
vote
2
answers
47
views
NFA to recognize the language ${ab}$
In Michael Sipser's Introduction to the Theory of Computation, Example 1.56 shows how to convert $\left(\text{ab }\cup\text{ a}\right)^*$ to an NFA. It builds up from the smallest subexpression to ...
- 113
0
votes
0
answers
12
views
A simple clarification on polynomiality of sequential construction of Turing Machines through plus construction
Suppose our original $NDTM$ $M_0$ has $N<2^t$ number of acceptance paths. We construct $r$ different $NDTM$s $M_1,\dots,M_r$ with each with $m_1,m_2,\dots,m_r$ acceptance paths respectively where $...
- 17
1
vote
1
answer
63
views
Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?
An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide ...
- 221
-2
votes
1
answer
31
views
How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?
Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method
I end up with this:
My ...
2
votes
2
answers
88
views
Is ε a part of alphabet or property of alphabet and NFA in FA
I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following:
3rd point of the above image is the ...
1
vote
1
answer
42
views
Implications of Savitch's theorem
I'm trying to figure out if the following statements are true:
• Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$.
• Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$.
• ...
- 369
0
votes
0
answers
31
views
Use NFA to express the acceptance of a rule
$\Sigma$ is letter set $\{a, b\}$. for word $w \in \Sigma^{*}$ and 2 language $L_{a}, L_{b} \subseteq \Sigma^{*}$ defined on $\Sigma$, we define language $w\left\{a \mapsto L_{a}, b \mapsto L_{b}\...
- 163
0
votes
0
answers
28
views
Algorithm to remove null transitions from an NFA?
I have an NFA represented as a vector<set<transition> > in C++. (Indices correspond to states, each index keeping a set of all transitions from the ...
- 1
3
votes
1
answer
39
views
Build an automaton from a given automaton to prove regularity of more complex strings
let $L$ be a regular language, and let $A=\{\Sigma, Q, q_0, F, \delta\}$ be a DFA such that $L = L(A)$.
I need to prove that $$L_p=\{xy\in\Sigma^*\mid\delta(q_0, y)=p\text{ and } \delta(p, x)\in F\}$$ ...
- 241
1
vote
1
answer
70
views
Use NFA to express the left quotient of the language of a DFA with respect to the language of another DFA
Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*.$
$L_1 \triangleleft L_2 = \{w\in \Sigma^* \mid \exists v\in L_1, vw \in L_2\}$
For clarity, here is python code that shows $L_3 \triangleleft L_4$:
<...
- 163
1
vote
1
answer
108
views
Can a nondeterministic Turing machine improve upon a P-time problem?
Linear search is solvable in O(n) time by a deterministic Turing machine. If we apply a nondeterministic Turing machine to the problem, can we solve the decision problem "Is $x$ in the array $A$?&...
- 1,024
0
votes
0
answers
36
views
If P = NP then EXP^P = NEXP^NP?
I believe that if P = NP, then that would imply EXP = NEXP (because of the padding argument), and then EXP^P = NEXP^NP (we could replace EXP with NEXP since they are equal, and replace P with NP, ...
0
votes
0
answers
44
views
How to convert a null state transition in nfa to dfa
i am looking to convert regular expression 0* 1* to deterministic finite automaton (DFA)
I have tried creating the NFA for the regular expression as given in the above image,
From the regular ...
- 1
1
vote
0
answers
54
views
Confused about the concept of deciding in nondeterministic Turing machines
I read this discussion before.
However i’m still confused. I used to think a language decided by a NTM if for every input $w$ in $\Sigma^*$, all of the branches in computation tree leads to a halting ...
- 358
0
votes
0
answers
21
views
If a problem is Cook-reducible to a problem in NEXP, is it in NEXP too?
I get why that would be true for EXP but cannot extend the argument to NEXP.
2
votes
0
answers
30
views
Definition of nondeterministic transition system in Principles of Model Checking
In Sec 2.1 of Principles of Model Checking, by Christel Baier and Joost-Pieter Katoen, the authors talk about what constitutes a deterministic transition system (T.S.), and mention two kinds - action-...
- 262
0
votes
0
answers
20
views
How to deal with epsilon transitions while converting NFA to DFA? (My start state only has outgoing epsilons)
The start state(S0) of my NFA has 2 outgoing epsilon transitions to S1 and S2, and, S1 and S2 have further transitions, and are disjoint of each other. So do I consider {S1,S2} as one state while ...
- 1
0
votes
0
answers
35
views
Can a 2-tape nondeterministic TM simulate a k-tape nondeterministic TM in the same time?
I've seen that we can simulate deterministic TMs with two tapes (Hennie and Stearns), but is there a way to prove this for nondeterministic TMs?
- 33
0
votes
0
answers
7
views
CONVERTING NFA TO RE [duplicate]
How do I obtain the regular expression of this NFA?
I have only done exercises where I obtain the RA from NFAs with only two states or when the third state is an accepting state and I simply follow ...
- 1
1
vote
1
answer
37
views
How can I know if more non-determinism can be used in an NFA?
I have to give the transition diagram of an NFA accepting all strings that are not empty and start and end with the same symbol, I should also use non-determinism as much as possible (language is {0,1}...
- 123
0
votes
1
answer
29
views
How to simulate an NTM using a DTM?
I've seen questions about how an NTM could simulate a DTM and this seems pretty straightforward to me. However, my text book says you can also simulate an NTM using a DTM.
How would this work? I'm ...
- 29
1
vote
1
answer
103
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. ...
- 111
1
vote
1
answer
30
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 ...
- 273
3
votes
1
answer
225
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 ...
- 31
3
votes
1
answer
64
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
1
answer
124
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 ...
- 39
0
votes
2
answers
568
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
...
- 39
0
votes
1
answer
22
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 ...
- 27
2
votes
1
answer
81
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
2
answers
90
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
0
answers
92
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,...
- 72
4
votes
2
answers
95
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
1
answer
48
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 $
...
- 113
1
vote
2
answers
80
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 ...
- 137
1
vote
2
answers
152
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-...
user139795
3
votes
1
answer
495
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$ ...
- 47
2
votes
1
answer
52
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(...
- 121
3
votes
2
answers
188
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.
...
- 47
0
votes
1
answer
110
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}...
- 1
3
votes
1
answer
83
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
1
answer
61
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,824
2
votes
1
answer
88
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 :...
- 125