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
4 votes
1 answer
65 views

Translating non-deterministic finite automata with counters to deterministic ones

I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, ...
136's user avatar
  • 141
0 votes
0 answers
29 views

How to convert NFA with multiple start states to NFA with single start state without epsilon transition?

I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition. But I want to know how can I do so without epsilon transition Here's my idea Suppose s1 and ...
Archaic's user avatar
0 votes
0 answers
16 views

Why nondeterministic decider for $ HAMPATH $ runs in polynomial time?

( Source: Introduction to the theory of computation, Michael Sipser, 3rd edition ) I know the computation-time of a non-deterministic Turing machine ( NTM ) which is a decider is defined to be the ...
flamel12's user avatar
  • 233
1 vote
0 answers
25 views

Non-Deterministic Turing Machine That Accepts RE-R language

As far as I know for Non-Deterministic Turing Machine (NTM) there are 4 kind of branches: An input is accepted if there is at least one node in the tree that is an accept. An input is rejected if all ...
Yuval's user avatar
  • 11
0 votes
0 answers
56 views

Constructing a PDA for $L=${$\exists i,k\in \mathbb{N} : |w|=2k, w_i \neq w_{k+i}$}

I have the main idea, yet I'm uncertain on how to construct this PDA (in terms of states, transitions) We can assume the alphabet $\Sigma$ is {$0,1$}, proving for $\Sigma=${$0,1$} is a sufficient ...
Aishgadol's user avatar
  • 315
0 votes
0 answers
31 views

Proving existence of NFA with specific amount of vertices

For every $i$ we define $\Sigma_i=${$1, 2, ..., i$} and a language over said $\Sigma_i$: $L_i=${$w\in \Sigma_i^*| \exists \sigma \in \Sigma_i :\sigma$ does not appear in $w$} And I'm asked to prove ...
Aishgadol's user avatar
  • 315
0 votes
1 answer
36 views

Does a non-deterministic Turingmachine reach every possible result?

I have problems to imagine a non-deterministic Turingmachine. Let's make an example: There is the problem of a Vertexcover. Let $G=(V,E)$ be an undirected graph and $k\geq 0$. The question is whether ...
mathquester's user avatar
0 votes
1 answer
55 views

Is there a typo in this excerpt from the book?

Michael Sipser's Introduction to Theory of Computation: Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a ...
Sbeve's user avatar
  • 51
1 vote
1 answer
461 views

Getting an NFA with only one initial and final state without epsilon transitions

Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions,...
ricardorr's user avatar
  • 115
2 votes
0 answers
46 views

Proving the language 2-SIMPLE-PATH is in NL

The Question I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c} \mathsf{there\;are\;two\;different}\\ \mathsf{simple\;paths\;from}\;s\;\...
snatchysquid's user avatar
1 vote
1 answer
135 views

What is the smallest NFA you can design for {a^n : n =/= 1003}

What is the smallest NFA that could be design for a^n where n!=1003? I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
staz6's user avatar
  • 25
0 votes
0 answers
43 views

Is there any way to tell which states are final states in a finite state automata given only its grammar?

Problem In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
Brett Smith's user avatar
3 votes
1 answer
986 views

When converting a epsilon NFA to NFA to DFA, how to handle the start state?

Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3 We know when converting from epsilon NFA to NFA, we apply the following formula for ...
Pratik Hadawale's user avatar
0 votes
1 answer
323 views

Conversion of epsilon NFA to DFA, handling epsilon transitions

I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs" Case 0: Michael Sipser asks us to handle ...
Pratik Hadawale's user avatar
1 vote
1 answer
217 views

Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states

Let's say we have a NFA as follows: It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon My question is do we take epsilon transition ...
Pratik Hadawale's user avatar
0 votes
1 answer
196 views

Confusion regarding the intuition behind epsilon transition in NFA

I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 ) Let's use this E-NFA as an example My question is, do we ...
Pratik Hadawale's user avatar
0 votes
1 answer
259 views

When converting from nfa to dfa, do we always ignore the trap state?

Let's say we have a NFA such as follows: We know it's equivalent DFA is follows, after minimization: We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of ...
Pratik Hadawale's user avatar
2 votes
0 answers
72 views

constructing non-trivial graph with known shortest Hamiltonian path

I'm interested in testing some Traveling Salesperson (TSP) greedy approximation algorithms for finding the shortest Hamiltonian path for very large graphs. Assume I can construct whatever graph I ...
Russ's user avatar
  • 121
0 votes
0 answers
36 views

Is it correct to describe a process as "nondeterministic" if it's input isn't necessarily identical?

This question isn't about the code below; however, I am using this as an example. In the below example, the break statement gets executed seemingly randomly when the mouse button is clicked; it's ...
stackhatter's user avatar
0 votes
0 answers
23 views

How are we sure choose is going to halt? question regarding a section from Elaine Rich's Automata, Computability and Complexity book?

I have a problem regarding the choose algorithm, I provide the algorithm's definition and it's use in the book,I attached a picture for the Illustration and for how the algorithm is used. choose (x ...
AlexG's user avatar
  • 11
3 votes
0 answers
42 views

Given a complexity class C for problems which can be solved using exponential time and an exponential number of random bits. C ⊆ NEXP?

There must be a complexity class C that includes exactly the problems that can be solved in exponential time and having access to a truly random coin (which in turns implies that you will be able to ...
Alonso Montero's user avatar
0 votes
2 answers
579 views

DFA and NFA Equivalence Proof

I'm taking a Theory of Computation class and we went over the proof to show that for any NFA there is an equivalent DFA, which I understand the proof fully in this case. But if it were in reverse, for ...
KJC_'s user avatar
  • 1
1 vote
2 answers
87 views

Consequences of the Halting Problem

The halting problem is semi-decidable. Does that mean that: If a program terminates it can always be established/determined? If a program does not terminate It can sometimes be established/...
RFV's user avatar
  • 141
10 votes
4 answers
2k views

Probabilistic methods for undecidable problem

An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic ...
Student's user avatar
  • 219
0 votes
1 answer
326 views

Meaning of lambda-transitions in npda

It is for me unclear how I can derive from a npda whether the lambda-transition means “I don’t care which symbol I read” or “I have read all the symbols”. For example, see the following automata: If ...
Ronald's user avatar
  • 89
0 votes
0 answers
280 views

Non-deterministic Pushdown Automaton to Context-Free Grammar

While doing the exercise about questions about transforming NPDA to CFG, I encountered the following question: Find a CFG for the following NPDA $M = (\{q_0, q_1\}, \{a, b\}, \{A, z\}, \delta, q_0, z, ...
Uduru's user avatar
  • 101
-1 votes
1 answer
58 views

Does a random phenomenon have a pre defined probability distribution? what does it mean for something to be random?

While studying Shannon's notion of perfect secrecy I came upon the idea that a bit is perfectly random if it happens to be 0 or 1 with an equal probability. What does this mean? Also, what can we say ...
Kashish's user avatar
0 votes
0 answers
49 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 ...
genus's user avatar
  • 1
1 vote
1 answer
216 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 ...
john doe's user avatar
  • 155
1 vote
1 answer
121 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 ...
Benicio Agüero's user avatar
1 vote
1 answer
195 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)$. ...
Benicio Agüero's user avatar
0 votes
0 answers
39 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 ...
heythere's user avatar
0 votes
1 answer
51 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, ...
Seonix's user avatar
  • 13
1 vote
2 answers
461 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 ...
csmathhc's user avatar
  • 113
1 vote
1 answer
78 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 ...
Dannyu NDos's user avatar
-2 votes
1 answer
72 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 ...
Pratik Hadawale's user avatar
2 votes
2 answers
151 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 ...
Pratik Hadawale's user avatar
1 vote
1 answer
88 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)$. • ...
SVMteamsTool's user avatar
3 votes
1 answer
43 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\}$$ ...
CforLinux 's user avatar
1 vote
1 answer
104 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$: <...
AsukaMinato's user avatar
1 vote
1 answer
173 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$?&...
Björn Lindqvist's user avatar
0 votes
0 answers
65 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, ...
Alonso Montero's user avatar
0 votes
0 answers
211 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 ...
Archi 's user avatar
1 vote
0 answers
131 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 ...
Omid Yaghoubi's user avatar
0 votes
0 answers
25 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.
user453758's user avatar
2 votes
0 answers
44 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-...
Motorhead's user avatar
  • 272
1 vote
1 answer
41 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}...
Sergio's user avatar
  • 123
0 votes
1 answer
124 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 ...
Matthias K.'s user avatar
1 vote
1 answer
220 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. ...
Ahmed Magdy's user avatar
1 vote
1 answer
42 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 ...
sandeepkunkunuru's user avatar

1
2 3 4 5
8