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 vote
1 answer
22 views

Is the set of languages with verifiers running in polynomial time equal to the set of languages decidable by an NTM running in polynomial time?

I have seen two definitions for the set $NP$. One is that it is the set of languages decidable by a nondeterministic Turing machine (NTM) running in polynomial time, and the other is that it is the ...
Wisdom Iwueze's user avatar
3 votes
2 answers
134 views

in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?

in $\epsilon$-NFA (NFAs involving $\epsilon$ transitions) when we have $\epsilon$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every ...
math boy's user avatar
  • 353
1 vote
1 answer
51 views

Proof that nondeterministic TM runs in exponential time

Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. ...
wytubev's user avatar
  • 13
0 votes
2 answers
35 views

NFAs that accept a regular language

Just a quick question about regular languages and which NFAs accept them: If I were to draw an NFA that accepts a particular regular language, does that mean the NFA can only accept strings in that ...
Derek Kwon's user avatar
4 votes
3 answers
698 views

Notation in NFA, DFA diagrams and language

I've only recently started learning about deterministic/nondeterministic finite automata and languages and I'd like some clarification on common notation used to describe languages. A 0 or 1 raised to ...
Derek Kwon's user avatar
1 vote
1 answer
63 views

Why can't we prove closure under concatenation using DFA?

I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to ...
hxdshell's user avatar
1 vote
1 answer
113 views

How to construct complement of NFA universality?

Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal? I tried to use the fact that NFA-universality is PSPACE-...
NooneAtAll3's user avatar
2 votes
1 answer
86 views

Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$

From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
codeing_monkey's user avatar
0 votes
0 answers
133 views

Non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$

I was trying to figure out how can I construct a non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$ I looked at some of the proposed solutions here : Turing ...
Yarin's user avatar
  • 275
2 votes
0 answers
62 views

How to prove MIP is in NEXP

I was trying to understand the proof of MIP is inside NEXP. I was referring to Rutger's university scribes (link). They define MIP as a class with exponential proof, but that is not the definition I ...
Zee's user avatar
  • 243
4 votes
1 answer
77 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
2 votes
1 answer
219 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
  • 21
0 votes
0 answers
36 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
31 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
2 votes
1 answer
192 views

ALL_{NFA} is PSPACE-complete

Show that $ALL_{NFA}$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^*$} is $\text{PSPACE-complete}$. I've manged to prove that the langauge is in $\text{PSPACE}$. Indeed, it is easy to see ...
GeoArt's user avatar
  • 21
0 votes
0 answers
104 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
  • 355
0 votes
0 answers
34 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
  • 355
0 votes
1 answer
49 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
57 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
743 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
55 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
140 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
75 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
1k 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
402 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
424 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
272 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
520 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
82 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
3 votes
0 answers
44 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
890 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
91 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
595 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
550 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
59 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
309 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
  • 177
1 vote
1 answer
156 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
216 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
41 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
70 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
725 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
83 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
116 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
170 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
124 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
45 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
125 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
190 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$?&...
Stand with Gaza's user avatar

1
2 3 4 5
8