The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
28 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
34 views

Formal language properties and finite state machines [on hold]

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
36 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
56 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
62 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
38 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
221 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 ...
2
votes
1answer
63 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 ...
1
vote
0answers
26 views

Constructing a TM from empty string

Hey I want to construct a deterministic Turing Machine, which out of an empty string tapes six consecutive 1s when halt. I have a question, is it possible to create such without transitions from final ...
0
votes
0answers
50 views

Turing machine from empty string: verification and suggestions

So I must create a Turing machine which records from empty tape six consecutive 1s. I am allowed to use only 3 states. $z_2$ is the final state. Furthermore, it should be deterministic. Here is my ...
0
votes
2answers
126 views

How does an NFA use epsilon transitions?

In the picture I've provided, I'm trying to figure out what exactly this NFA is accepting. What's confusing me is the epsilon jump at q0. If a 0 is entered, does the system move to both q0 AND ...
4
votes
1answer
71 views

Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$). For example, $L=\{a^nb^n\mid ...
1
vote
1answer
28 views

Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol?

Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Say f is the transition function, why does having ...
1
vote
1answer
23 views

Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine

If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course ...
0
votes
1answer
48 views

Non-deterministic algorithm to check if a list has some given value

I know that I can build a non-deterministic algorithm with a CHOICE function that verifies if a value x is in an array in O(1) ...
4
votes
1answer
42 views

Using SMT solvers to generate random solutions to given predicate

I am interested in generating random solutions to predicates. I only need SMT for integers with the following predicates/functions <, >, <=, >=, ==, !=, +, * The algorithm I want should produce ...
3
votes
1answer
22 views

The communication complexity of non-equality

I'm familiar with the fooling set technique to obtain lower bounds for communication complexity protocols. The most basic example is the equality function for which the diagonal matrix gives the ...
2
votes
1answer
102 views

NFA - string acceptance (decision problem) test

I am interested in testing for a given string (w) whether it is in the language (L) defined by a nondeterministic finite automaton (A). I have some blurry point in my mind. What is the complexity of ...
3
votes
2answers
108 views

Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.) However, there are different kind of algorithms, such as deterministic, ...
4
votes
1answer
346 views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
0
votes
1answer
41 views

NFA state complexity for the complement of EPAL restricted to a fixed length

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA ...
1
vote
0answers
103 views

K -> 2 tape reduction for nondeterministic Turing machines

How to I show that any language in NTIME(T(n)) can be accepted by a non-deterministic 2-tape O(T(n)) time-bounded Turing machine, with modifiable input tape? I've seen the k to 2 tape reduction for ...
2
votes
2answers
103 views

Algorithms which are both deterministic and non-deterministic

I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms ...
1
vote
0answers
110 views

Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
-1
votes
1answer
53 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 ...
7
votes
2answers
245 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
87 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^* : ...
0
votes
3answers
905 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
144 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 ...
-1
votes
1answer
51 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
24 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
44 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
61 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?
15
votes
10answers
1k 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
130 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
77 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
191 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
350 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
67 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
101 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 ...
4
votes
3answers
1k 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
357 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
104 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
95 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
99 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
494 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
1k 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
185 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
474 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 ...