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!

Filter by
Sorted by
Tagged with
-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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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)$. ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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)$. • ...
user avatar
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}\...
user avatar
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 ...
user avatar
  • 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\}$$ ...
user avatar
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$: <...
user avatar
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$?&...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
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.
user avatar
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-...
user avatar
  • 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 ...
user avatar
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?
user avatar
  • 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 ...
user avatar
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}...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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,...
user avatar
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 ...
user avatar
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 $ ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
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$ ...
user avatar
  • 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(...
user avatar
  • 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. ...
user avatar
  • 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}...
user avatar
  • 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 ...
user avatar
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$?
user avatar
  • 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 :...
user avatar

1
2 3 4 5
8