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
Filter by
Sorted by
Tagged with
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 ...
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
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 vote
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
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 ...
1 vote
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)$. ...
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
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
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
12 views

• 163
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
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
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
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
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, ...
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 vote
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 ...
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.
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
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 ...
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
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 vote
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
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 ...
1 vote
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
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 ...
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
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
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
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
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 ...
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 ...
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 ...
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,...
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 ...
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
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
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-...
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
52 views

• 1
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
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
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 :...