The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
33 views

NDFA associated with language L

Let A = $(Q, \Sigma, \delta, S, F)$ be a deterministic finite automaton associated with the language $L \subseteq \Sigma^*$ $L' = \{y \in \Sigma^*:\exists x\in L. |x| = |y|\}$ $L \subseteq ...
-2
votes
1answer
21 views

Why it is said that LBA is a non deterministic Turing Machine

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
13
votes
8answers
664 views

Why is non-determinism useful concept?

An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state. When we ...
2
votes
1answer
34 views

Why Deterministic PDA accepts $\epsilon$ input but DFA not

I was going through a deterministic PDA that accepts $wcw^R$ (described in Ullman's textbook), in which the last transition is given as $(q_1,\epsilon, Z_0)\to(q_2,Z_0)$, where $q_2$ is the final ...
-1
votes
1answer
63 views

A NPDA for the language $L = \{w \mid w \in \{a,b,c\}^*, n_c(w) = n_a(w) + n_b(w)\}$

Consider the language $L = \{w, w \in \{a,b,c\}^*, n_c(w) = n_a(w) + n_b(w)\}$, where $n_q(\omega)$ is defined to be "the number of $p \in \omega$. I have tried a couple of PDA's that follow this ...
6
votes
1answer
163 views

Why is this function computable in $O(n^{1.5})$ time?

My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number ...
2
votes
1answer
70 views

Creating a Deterministic Push Down Automata

I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself. ...
1
vote
2answers
56 views

2 threads accepted at the same time [closed]

Assuming we have an automaton that simultaneously accepts a string on two paths. Would this mean that the construction of the NFA might be faulty? In other words; at the end of any string over any ...
0
votes
0answers
30 views

Non-deterministic finite state automoton [duplicate]

I am taking a course in the theory of computation and am trying to understand how to correctly design NFA's so that I can transform them into regex. I was wondering if I have Sigma={a,b} and need to ...
0
votes
0answers
85 views

Non determininstic finite state automata [closed]

I wanted to construct a NFA over sigma star, where sigma={a,b}, such that at least one of the last 2 symbols is an "a". I just wanted to make sure that this construction is correct. Original image ...
1
vote
3answers
136 views

Decidable languages kleene star closure - question on a proof

I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the ...
1
vote
1answer
103 views

how to solve NFA acceptance problem in polynomial time

I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires ...
2
votes
3answers
83 views

Relaxing the stack in a push down automata

Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol ...
1
vote
1answer
70 views

NFA for right left multiplication

Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ? The string "abcb" would be evaluated as (a(b(cb))) = a ...
-2
votes
2answers
89 views

help with the probability of acceptance of a Nondeterministic Pushdown automata

I have this nondeterministic pda: $$\Sigma= \{a,b,c\}$$ and $$ L=\{\omega\ \epsilon\ \Sigma^*\ |\ \omega\ = \alpha\beta\beta^R\gamma\ and\ \alpha,\beta,\gamma\ \epsilon\ \Sigma^*\ and\ |\beta|\ ...
0
votes
1answer
89 views

NFA to DFA convertion explanation

I've converted this NFA to a DFA and I get a similar soultion automata but I'm not sure if I really understand everything. Please correct me if I'm explaining it wrong, I would love some feedback. ...
1
vote
1answer
395 views

Maximum number of states in minimized DFA from NFA with $n$ states [duplicate]

If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$?
-2
votes
1answer
68 views

Proving $PH = NP$ [closed]

Show that if 3SAT is polynomial-time reducible to $complement of 3SAT$ then $PH = NP$. Above problem is Exercise problem from Arora and Barak, i don't know how to solve this problem,if anybody knows ...
-1
votes
2answers
82 views

Designing a DFA in which last fourth character is 1 [closed]

I have to design a DFA with last 4th character from end is 1. The alphabets are {0,1} for e.g. (Anything)1*** One way is to make an NFA and then convert it to DFA... But i am finding it quite ...
-1
votes
1answer
62 views

Do these languages both have DPDA? [closed]

We have these languages: $$L_1 = \{a^nb^na^mb^m \ | n \ge 0, m \ge 1\}$$ $$L_2 = \{a^nb^na^mb^{2m} \ | n \ge 0, m \ge 1\}$$ are both these languages NCFG? I guess that both of them are NCFG because ...
1
vote
1answer
86 views

Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions

I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk ...
3
votes
3answers
172 views

What does “deterministic” mean in the context of memory management?

At the time of writing, Wikipedia describes determinism as: "a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying ...
4
votes
2answers
199 views

Why do most scientists believe that P≠NP?

I read that most scientist don't believe that P=NP. This might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some ...
6
votes
2answers
115 views

Push Down Automatons “guess” - what does that mean?

I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted ...
6
votes
3answers
205 views

Algorithm to shrink a DFA by introducing nondeterminism?

This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question. I'm doing research where I'm trying to find the structure of complements of a ...
4
votes
3answers
151 views

Are there algorithms to exactly minimize NFAs which are sometimes efficient?

I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time ...
4
votes
1answer
145 views

Checking whether a directed graph on n vertices contains exactly 10*sqrt(n) strongly connected components is in non-deterministic logspace

I am studying now for a test in my complexity course. When I solved previous exams I saw the following question : Prove that the language $L$ of all directed graphs on $n$ vertices that contain ...
8
votes
3answers
399 views

Why is NFA minimization a hard problem when DFA minimization is not?

I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs? I'm not looking for a proof or anything like that--unless a proof is simpler to ...
7
votes
1answer
138 views

Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?

These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give ...
5
votes
1answer
121 views

Nondeterministic finite state machine without any initial state possible

Is it theoretically possible to have a nondeterministic finite state machine without any initial state or does it need at least one initial state?
2
votes
1answer
2k views

Converting an NFA to regex using GNFA algorithm?

So I've been trying to crack this for a long time and almost feel like I am going in loops about this question. Given the following NFA: Using the GNFA algorithm get the regular expression. I ...
6
votes
2answers
107 views

Classes of NFAs which allow efficient subset testing or unambiguity conversions

I'm doing some research regarding NFAs and inclusion problems with them. I know that in general, the inclusion problems, and converting to an unambiguous NFA, are both PSPACE-complete. I'm wondering, ...
1
vote
1answer
159 views

what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?

I saw this term "Glushkov NFA" at http://lambda-the-ultimate.org/node/2064 . Search engines are returning references to articles that use glushkov nfa, but nothing specific about the glushkov nfa ...
7
votes
2answers
105 views

Why is one often requiring space constructibility in Savitch's theorem?

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
1
vote
1answer
170 views

Closure of regular Language - Transition Function : Sipser Proof

I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser. I have ...
3
votes
2answers
237 views

Equivalence of NFA and DFA - proof by construction

I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set ...
4
votes
4answers
198 views

Are there real lexers that use NFAs directly instead of first transforming them to DFAs?

I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
3
votes
2answers
265 views

Non-deterministic Turing machine that halts on at least one branches of computation

I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing ...
8
votes
6answers
1k views

Can we say DFA is more efficient than NFA?

I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
2
votes
1answer
106 views

Non-deterministic algorithm for solving figure of 8

I am struggling in trying to figure out a non-deterministic algorithm for the following problem. Consider the following problem, called the figure-of-eight problem (FOE). An instance is an undirected ...
4
votes
1answer
123 views

What is prefix monotonicity?

I have a background in computer architecture and only cursory understanding of process networks. For a paper I am writing I need to understand prefix monotonicity properly. For now I have "a stream ...
5
votes
1answer
120 views

What is the state of the art in encapsulated search in functional logic programming?

I am particularly interested in solutions to the problem that encapsulated search can depend on the order of evaluation. According to [1], encapsulated search in PAKCS depends on the order of ...
2
votes
0answers
182 views

Logarithmic space difference between deterministic and non-deterministic algorithms

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
1
vote
1answer
69 views

Are any problems in P known to have logarithmic-time-verifiable certificates?

Problems in NP have certificates which can be verified in polynomial time. It seems conceivable that there could be problems in P which have certificates which can be verified in logarithmic time. ...
1
vote
1answer
208 views

How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$: Write a ...
1
vote
2answers
181 views

Visualizing a Non Deterministic Decider

I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization ...
12
votes
2answers
167 views

Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
2
votes
1answer
81 views

Superpolynomial time set such that SP=NSP is known?

Are there any superpolynomial time set $\mathsf{SP}$ in between $\mathsf{P}$ and $\mathsf{EXPTIME}$ such that the problem $\mathsf{SP}=\mathsf{NSP}$ has a known answer? UPDATE: It must be defined by ...
12
votes
4answers
2k views

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
12
votes
3answers
340 views

How to prove that DFAs from NFAs can have exponential number of states?

All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...