Skip to main content

Questions tagged [linear-bounded-automata]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
39 views

Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

The membership problem $A_{LBA}$ for a deterministic $LBA$ is decidable because the number of configurations that a $LBA$ can assume is finite. Since this number is also finite for a non-deterministic ...
Marcus's user avatar
  • 141
0 votes
1 answer
93 views

recursively enumerable and linear bounded automaton

I have a question about linear bounded automaton. Is it false that every recursively enumerable language is recognized by a LBA ? Because LBA has limited tape size so not all recursively enumerable ...
MathJunior's user avatar
1 vote
1 answer
102 views

Language of equal numbers of as, bs, cs in any order not context-sensitive?

In his book "Foundations of Computing", professor Allison shows an example of "language of equal numbers of as, bs, and cs, but in any order", formally: $L = \{ w \in \{a,b,c\}^*\ |...
Barney's user avatar
  • 167
2 votes
1 answer
471 views

Why is $E_{LBA}$ undecidable if $A_{LBA}$ is decidable

A linear bounded automaton (LBA) is a restricted TM with finite tape. Let $A_{LBA} = \{\langle M, w \rangle | M$ is an LBA that accepts string $w \}$. It can be shown that $A_{LBA}$ is decidable: ...
curiouscupcake's user avatar
2 votes
1 answer
37 views

Are there decidable non-trivial properties of a LBA's accepted language?

The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable? Given a LBA, can you decide whether there exists an input ...
user10385242's user avatar
1 vote
2 answers
546 views

Is it decidable whether a TM is a LBA?

Given an arbitrary TM, can you decide whether it's a LBA?
user10385242's user avatar
3 votes
1 answer
323 views

Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$

I need to construct linear bounded automaton for the language $L = \{ a^{n!} : n \geq 0 \}$. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a....
Ajinkya Taranekar's user avatar
2 votes
2 answers
245 views

How to we prove if a right linear language is ambiguous?

Considering the following language as an example: $$\begin{align} S &\rightarrow aS \mid bA \\ A &\rightarrow bA \mid aB \mid aD \mid \varepsilon \\ B &\rightarrow aB \mid \varepsilon \\ D ...
A. K.'s user avatar
  • 143
0 votes
1 answer
127 views

Does CSL contain an empty string or not? Is empty string accepted by LBA or not?

I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite ...
A Paul's user avatar
  • 176
1 vote
2 answers
1k views

Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?

Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get ...
A Paul's user avatar
  • 176
2 votes
1 answer
4k views

Difference between linear bound automata and a Turing machine

Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a ...
Vamsi Shankar's user avatar
1 vote
1 answer
272 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 ...
siracusa's user avatar
  • 360
0 votes
1 answer
176 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 ...
Edmundo Del Gusto's user avatar
0 votes
1 answer
930 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 ...
False Equivalence's user avatar
6 votes
1 answer
2k 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 ...
Andrey Lebedev's user avatar
0 votes
2 answers
338 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?
user's user avatar
  • 215
2 votes
1 answer
381 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?
SiluPanda's user avatar
  • 549
0 votes
0 answers
31 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-...
TandyZ's user avatar
  • 1
4 votes
2 answers
662 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 ...
juhist's user avatar
  • 283
1 vote
1 answer
985 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 ...
caffein's user avatar
  • 175
1 vote
1 answer
788 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 ...
Arka Pal's user avatar
  • 311
1 vote
2 answers
2k 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 ...
Caffeine's user avatar
2 votes
1 answer
229 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 ...
Jack's user avatar
  • 175
2 votes
1 answer
711 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 ...
Xiao Liang's user avatar
3 votes
0 answers
138 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 ...
Radu Stoenescu's user avatar
0 votes
1 answer
615 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 ...
Hans Christian's user avatar
0 votes
1 answer
121 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 ...
Winston's user avatar
  • 143
12 votes
2 answers
3k 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 ...
Ben I.'s user avatar
  • 1,710
5 votes
0 answers
449 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. ...
L.Yi's user avatar
  • 63
2 votes
1 answer
590 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 ...
O.S.'s user avatar
  • 23
4 votes
1 answer
239 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, ...
mak's user avatar
  • 205
3 votes
1 answer
119 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. ...
NedaHn's user avatar
  • 135
5 votes
0 answers
211 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 ...
Richard's user avatar
  • 51
20 votes
4 answers
3k 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 ...
babou's user avatar
  • 19.5k
1 vote
1 answer
220 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 ...
odu9's user avatar
  • 165
7 votes
1 answer
2k 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, ...
Thomas Klimpel's user avatar
3 votes
0 answers
210 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 ...
lukas.coenig's user avatar
1 vote
1 answer
91 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 ...
alex440's user avatar
  • 175
19 votes
3 answers
7k 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 ...
user5507's user avatar
  • 2,191
-1 votes
2 answers
2k 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?
user5507's user avatar
  • 2,191
2 votes
2 answers
590 views

Complements of Linear Bounded Automata?

Would switching the accept and reject states of an LBA A create a new LBA we'll say A' in which the language of A' is the complement of the language of A? I believe the answer is yes just by working ...
IABP's user avatar
  • 272
3 votes
2 answers
441 views

Recognizing loops in computation on LBA

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 ...
Mahdi's user avatar
  • 579