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!

learn more… | top users | synonyms

6
votes
1answer
108 views

Are there any known lower-bounds for complexity on Non-determinsitic machines

For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time. Are they any problems where we have known lower bounds for ...
2
votes
2answers
41 views

Size comparison of NFA and minimal DFA [duplicate]

Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? ...
5
votes
2answers
84 views

How do nondeterministic Turing machines compute general function problems?

(Hope this hasn't been asked before, but I didn't find anything.) In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. ...
2
votes
2answers
97 views

How are games like chess provably harder than NP?

From this question, I had the debate about how problems harder than NP are proved. I said that intuitively I understand it as (from this video explaining that some problems are provably harder than ...
3
votes
2answers
325 views

What complexity class would this version of generalized chess fall?

By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof ...
5
votes
1answer
182 views

How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
0
votes
0answers
33 views

Minimize NFA with epsilon transition

I have an NFA with epsilon transition, I would remove the epsilon transitions, but I do not know if I have to use Hopcroft algorithm or another algorithm. Can you help me? Thanks
-2
votes
1answer
38 views

NFA with epsilon transition

I need to understand the epsilon transition for NFA, for example I have an NFA with four states q0, q1, ...
0
votes
3answers
92 views

Design an NFA to accept a, ad, abc, abd, but not e, abcd?

I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that? Updated I modified the diagram in another attempt:
1
vote
1answer
83 views

PDA for all non-palindromic strings of even length

I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$. I already turned it in, but I know I had it ...
1
vote
1answer
37 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
-1
votes
1answer
31 views

Why do these NFAs need epsilon transitions?

In the picture below, I'm trying to figure out why there's a need of epsilon in there and what would be the difference if we didn't put epsilon.
1
vote
1answer
55 views

Non deterministic turing machine

Does a non deterministic turing machine which is a decider halt on all branches for all inputs?? I know it must halt on all branches for a string not in language but for a string in language ,NDTM ...
4
votes
1answer
164 views

Brzozowski algebraic method for NFA

Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA some nodes have multiple in/outgoing edges single start state there might be multiple final states a state ...
3
votes
1answer
40 views

How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$

Following is a theorem from Sanjeev Arora and Boaz Barak I am unable to prove : If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p_2$. The previous similar theorem was ...
1
vote
1answer
329 views

Deterministic vs. Non-Deterministic PDA?

The following is an example of language $a^nb^n$ where $n \geq 1$ From what I have heard that in finite state machines if you see epsilon moves, then it is NFA otherwise it is DFA. But in this case,...
2
votes
1answer
33 views

How convert instances of a language efficiently into 3SAT instances?

The following question is from Sanjeev Arora and Boaz Barak ( not homework ) Show that for every time constructible $T:N \to N$, if $L \in NTIME(T(n))$ then we can give a polynomial-time Karp ...
2
votes
1answer
41 views

Why is my trivial reasoning for $PSPACE = PH$ wrong?

If $\sum_i^p$ denotes $ith$ polynomial hierarchy. And $\sum_i TIME( T(n) )$ denotes set of languages accepted by $T(n)$ time alternating Turing machine $M$ whose initial state is labeled $\exists$ and ...
4
votes
2answers
272 views

NSPACE for checking if two graphs are isomorphic

I was studying nondeterministic Turing Machines and came across the following question: Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are ...
3
votes
2answers
35 views

How do cycles of non-consuming transitions in NFAs influence their halting properties?

I am in a class that is going over NFAs. The way they are described is a set of states, one of which is the start state, zero or more are accept states, and one or more transitions between them, which ...
7
votes
1answer
407 views

How can I show that the Cook-Levin theorem does not relativize?

The following is an exercise which I am stuck at ( source: Sanjeev Arora and Boaz Barak; its not homework ) : Show that there is an oracle $A$ and a language $L \in NP^A$ such that $L$ is not ...
2
votes
1answer
111 views

Why is simulation by non deterministic Turing machine faster than a deterministic one?

A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and ...
4
votes
1answer
110 views

NL and NP compute different binary relations, so what?

Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input ...
3
votes
1answer
40 views

How Can I Recognize When to Use ε-Transitions in an NFA?

I am learning about finite automata for the first time. I am having trouble understanding the purpose of ε-transitions in an NFA, which seem to be crucial to counting the number of states in an NFA ...
3
votes
2answers
202 views

How does the NFA decide in a state where there are multiple equally valid “next states”?

How does the NFA decide in a state where there are multiple equally valid "next states"? Such as here: How does it decide on which state it takes to with 1?
10
votes
3answers
537 views

How do I verify that a DFA is equivalent to a NFA?

I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is ...
-1
votes
1answer
66 views

What input does this NFA accept?

I'm trying to find out what strings this NFA would accept. From what I understand, an empty string would work, as well as any string that has nothing but 0's. But for strings containing 1's, I'm a ...
0
votes
1answer
33 views

Finding an automaton with a given number of states

Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^*$. My main problem is that to check for a string of length 4 (...
0
votes
2answers
60 views

Can a deterministic language be accepted by a deterministic Push Down Automaton?

I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic ...
3
votes
1answer
96 views

How to remember NFA's choice on a certain computation?

I'm working on solving the question answered at this page but with different values at the table, my alphabet is {a,b,c} Words that have the same right- and left-associative product Currently I'm in ...
1
vote
0answers
43 views

Dangling else determinism

The natural grammar for dangling "else" is ambiguous. But there exists an unambiguous version of the grammar that links the "else" to last uncompleted "if" statement. Is this version also ...
4
votes
2answers
345 views

If the universe were predetermined, would non-deterministic automata still make sense?

If the universe were governed by predeterminism (i.e. some deity decided in advance how everything, ever, would play out), would the notion of non-deterministic automata make sense? Or would it not, ...
0
votes
1answer
67 views

What language should this NFA recognise?

I am trying to figure out which language does the following NFA (taken from a Sipser's book "Introduction to theory of computation") recognise From my understanding, this NFA accepts strings that ...
5
votes
1answer
552 views

Can we show that non-determinism adds no power, for some specific running time?

$NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$ $P = \cup_{k \in \mathbb{N}} TIME(n^k)$ Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$? For how large of a $k$ can we show the above ...
5
votes
2answers
94 views

What real-world computer languages cannot be described by deterministic grammars?

Are there any examples of real-world computer languages that are non-deterministic? By computer languages I include programming languages, markup languages, query languages, modeling language, ...
1
vote
1answer
43 views

Non-deterministic algorithms and Tautologies

I am studying the lecture The Complexity of Propositional Proofs. ​Here there is a definition together with a discussion (page 3). I don't understand that discussion. Let $F$ denote the set of ...
2
votes
0answers
35 views

How to construct an NFA [duplicate]

I am trying to learn how to construct an NFA state diagram. $$M = \{q0, q1, q2\}, \{a,b\}, \delta, q0 , \{q2\}$$ $δ(q0,a) = q0; \delta(q0,b) = {q0,q1}; \delta(q1,a)= {q0, q2}; \delta(q1,b) = {q1}; \...
8
votes
1answer
390 views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
0
votes
0answers
10 views

Language of strings of lengths that are prime is regular? Is C^* regular? [duplicate]

With $\Sigma = \{a\}$ I want to see if a language $C = \{a^p \ | \ p \ \text{is prime}\}$ is regular and whether or not $C^*$ is regular. How would I go about showing whether $C$ or $C^*$ are regular?...
3
votes
1answer
66 views

When does a PDA split?

In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. ...
2
votes
0answers
53 views

Use DFA minimization on LR(1) states

I have recently started reading more about context-free parsing techniques, in particular LR parsing. As I have read, LR state transition graph (or table(s)) used for finding handles in sentential ...
1
vote
0answers
54 views

NFA that accepts binary strings starting with 1 and with at least 01, or at least 010, or both

Im not sure if I am understanding this question correctly. Its a problem without a solution in my text. Starting with 1, and at least 01 or at least 010 or both these substrings..... So a regular ...
1
vote
1answer
54 views

Executing an NFA

I am trying to verify that the NFA below does not accept babba. However, when I tried to do it by hand I must have made a mistake: $$\{q_1\}, \{q_2,q_3\}, \{q_1, ...
12
votes
5answers
533 views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
5
votes
3answers
137 views

Are deterministic and nondeterministic Cellular Automata equivalent?

It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs. I ...
7
votes
1answer
107 views

Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model

From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs ...
-1
votes
1answer
391 views

Converting this NFA to Turing Machine

I'm asked to choose a DFA and convert it to NFA and then convert it to Turing machine... I have done the first two parts as follows: DFA: --> NFA: --> Turing machine: ??? I haven't found ...
0
votes
0answers
69 views

extended transition function for NFAs

Below I am using a DFA transition function that is extended to accept words instead of just symbols. Let's say it is given that the following information is true: $$\delta(q_0, 0^3) = \delta(q_0, 0^6)...
1
vote
0answers
107 views

Formal language properties and finite state machines [closed]

What are properties of a formal language? Which and how would they be needed to prove that some Non-Deterministic finite state machine can accept a given language?
-1
votes
1answer
100 views

NDTM for Graph Clique Problem in poly-time

I am having a doubt. This is my NDTM algorithm: GCP(G, k): generate a list with k distinct nodes from graph G generate an adjacency matrix, fill it with 1 if an edge exist, 0 otherwise check if ...