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

0
votes
0answers
28 views

Adjacency matrix and transitive Closure for delete epsilon transition NFA [closed]

I would to delete the epsilon transition from my NFA. I need to understand the transitive closure for automata; I want to create the adjacency matrix by it and at the present, I don't know if the ...
0
votes
0answers
31 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
35 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
89 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
60 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
31 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
29 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
54 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
148 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
35 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
223 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 ...
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
263 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
401 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
104 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
107 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
35 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
201 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
521 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
42 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
344 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
66 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
93 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
42 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
318 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 ...
3
votes
1answer
64 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
50 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
524 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
134 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
101 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
292 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
63 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, ...
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
94 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 ...
4
votes
3answers
203 views

Why doesn't parallelism necessarily imply non-determinism?

I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out. I understand the difference between ...
1
vote
1answer
69 views

How can I quickly guess if L is context-free or det. context-free?

I have a language, for example $\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\}$ $\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\}$ How can I see at a glance whether the language is deterministic ...
0
votes
1answer
43 views

Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
4
votes
4answers
468 views

What is determinism in computer science?

I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number ...
3
votes
2answers
140 views

Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement?

When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside ...