Questions tagged [linear-bounded-automata]

The tag has no usage guidance.

31 questions
Filter by
Sorted by
Tagged with
19 views

Does a type-1 automaton always have to terminate?

For push-down automata it seems obvious to me that a program must always terminate (given the input is finite), because for each input symbol they advance until eventually they run out of symbols and ...
50 views

Decidability of the language of all deterministic LBA where all states are reachable

I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a) (a) L := { < A > | A is a DFSA, where all states are ...
33 views

Number of Configurations of LBA(Linear Bounded Automaton)

The lemma is: Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet. There are exactly $qng^n$ distinct configurations of $M$ for a tape of length $n$. I want know why LBA has ...
91 views

A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...
40 views

Are Linear Bounded Automatons Turing Complete?

Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape. But this causes them to not be Turing Complete? Why?
67 views

Undecidability of emptiness of LBA

How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?
27 views

Q: Calculating a MPI cluster throughtput from hardware latencies

Since i don't have a CS background in my career, Built up an openmpi compute platform which succesfully computes from a variable number of available nodes. call this whole, a mpi cluster having N^2 4-...
253 views

Is it possible to convert LBA into DFA?

Today I learned about an abstract class of machines called linear bounded automata. It is intended to model real-world computers that have a limited amount of memory. I have always thought that real ...
74 views

Show that $A_\mathrm{LBA}$ is PSPACE-Complete?

I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte. Say we proved it is in PSPACE. Now for PSPACE-HARD: I had an idea, which was very similar to some solution i found on the web- say we have a ...
201 views

Prove that it is undecidable whether a given LBA accepts a regular set

I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ...
470 views

Reduce undecidable language to decidable language?

What happens if I build the following mapping function from $A_{\mathrm{TM}}$ to $A_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A_{\mathrm{LBA}}$ is decidable): If $M$ accepts ...
106 views

What kind of languages can be recognized by a restricted one-tape deterministic Turing Machine?

During a lesson, our TA asked: What kind of languages can be recognized by a deterministic Turing Machine such that we can use only a tape portion that contains the input? My thoughts: my ...
252 views

A confusion about the Reduction via Computation History

[Updates: Thanks for @Raphael 's notification, I delete the screenshot of the book and type the $LaTex$ materials] In Sisper's Intro to the theory of Computation, there is a reduction method via ...
106 views

Algorithms to match regular expressions containing backreferences

I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like: ([a-c])x\1 which would match ...
182 views

LBA for $L = \{a^nb^{2n} \mid n\geq1 \}$

I want to construct a linear bounded automata for the language $L = \{a^nb^{2n} \mid n\geq1 \}$ . I know how LBA works but I don't have an idea how it can count the numbers of a's and check if the b's ...
67 views

Modified Linear Bounded Automata Language

We know that linear bounded automatons accept context-sensitive grammars. Now suppose that we modify the LBA such that any location of the tape except the input part can be changed.What language ...
2k views

Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines. However, Linearly Bounded Turing Machines are also ...
118 views

Time complexity of languages recognized by linear bounded automata with restricted number of writes

Suppose that $L$ is a language recognized by a linear-bounded automaton with the constraint that it can only change each of its input cells at most $t$ times each, where $t$ is some constant integer. ...
332 views

Why cannot we reduce the Emptiness problem of LBA to the Acceptance problem of LBA?

I am a little bit confused about the emptiness problem of the linear bounded automaton (LBA). I know that this problem is undecidable. However if we assume that is decidable, what could be wrong if we ...
117 views

Is every language in PTime also context-sensitive?

Context-sensitive languages are exactly those that can be recognised using linearly bounded automata, i.e., those in NSPACE(O($n$)). This subsumes all languages that can be recognised in linear time, ...
95 views

Restrictions to counter machines capturing LBA

As you know in computation theory, there is a simple programming language equivalent in power to Turing machines. It is described as follows: Values: natural numbers only, but of unlimited precision. ...
116 views

Is $E_{LBA}$ a Turing-recognizable language? [closed]

I know that $E_{LBA} = \{\langle M \rangle ~ \mid ~ L(M) = \emptyset \}$ is an undecidable language, but is it recognizable (recursively enumerable)? It seems that it's complement is recognizable ...
2k 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 ...
112 views

How does augmenting linear bounded automata tape alphabets increase memory?

A linear bounded automaton is a Turing machine that is restricted by memory. How would augmenting the tape alphabet of a linear bounded automaton increase its memory? While the memory that the ...
752 views

Is a LBA with stack more powerful than a LBA without?

Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful. A LBA with stack should not be Turing complete, ...
114 views

Is there a grammar type for deterministic LBA?

Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this ...
66 views

How can an LBA check legality of TM transitions without extra memory?

In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$. The reduction is proposed in the following manner: we receive a TM $M$ and a ...
5k views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
727 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?
In the case of LBAs (Linear Bounded Automaton), in writing a decider for the language $\qquad A = \{ \langle M,w\rangle \mid M\ \mathrm{LBA}, w \in \mathcal{L}(M) \}$ we reject the input after a ...