The tag has no wiki summary.

learn more… | top users | synonyms

-1
votes
1answer
48 views

Why is there still nondeterminism in my automaton?

I've been solving some exercises recently and it appears my answer was wrong for this particular example. The task is to convert this NFA into a DFA: My attempt is this: Now the tool I'm using ...
4
votes
0answers
68 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
7
votes
1answer
65 views

Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

Let $k\in \mathbb N$ I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : ...
-1
votes
3answers
168 views

Problem understanding DFA & NFA equivalence in Theory of Computation

Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction but my question is a bit different from that. I was reading Michael Sipser's ...
0
votes
4answers
131 views

How is a nondeterminisitic automaton running on an input?

A nondeterministic automaton, after reading an input symbol at some state, may jump into any of a (finite?) number of states. Does the automaton uniformly randomly choose one out of the several ...
0
votes
1answer
43 views

Random algorithm termination

Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 < p < 1$ and terminates with probability $1-p$. Does this algorithm terminate? On ...
-1
votes
1answer
25 views

Is there a software algorithm that can generate a non-deterministic chaos pattern?

Is there a software algorithm can generate a non-deterministic pattern or sequence? In Chaos theory, simple processes can create deterministic patterns, and psudo-random number generators can generate ...
1
vote
0answers
21 views

Upper bounds for $NP$ based on $NEXP = EXP$

It's open whether $EXP = NEXP \to P = NP$ (the other direction can be shown by padding). My question: has there been any progress along these lines at all? For example, can we show that $EXP = NEXP ...
1
vote
2answers
36 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
32 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?
12
votes
8answers
807 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
52 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
71 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
170 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
101 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
64 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
34 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
91 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
284 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
158 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
86 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
78 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
93 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
133 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
634 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$?
1
vote
1answer
97 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 ...
4
votes
3answers
230 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
212 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
128 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
218 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
160 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
180 views

Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

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 exactly ...
8
votes
3answers
472 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
152 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
126 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?
3
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
110 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
179 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
108 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
181 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
314 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
214 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
331 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
107 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
125 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
202 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 ...
2
votes
1answer
76 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
281 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 ...