Questions tagged [linear-bounded-automata]
The linear-bounded-automata tag has no usage guidance.
42
questions
0
votes
0
answers
31
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 ...
1
vote
1
answer
75
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\}^*\ |...
- 155
2
votes
1
answer
320
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: ...
- 294
0
votes
0
answers
37
views
Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]
We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
- 346
2
votes
1
answer
31
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 ...
- 131
1
vote
2
answers
498
views
Is it decidable whether a TM is a LBA?
Given an arbitrary TM, can you decide whether it's a LBA?
- 131
3
votes
1
answer
254
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....
2
votes
2
answers
220
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 ...
- 143
0
votes
1
answer
109
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 ...
- 178
1
vote
2
answers
875
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 ...
- 178
2
votes
1
answer
3k
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 ...
1
vote
1
answer
253
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 ...
- 360
0
votes
1
answer
160
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 ...
0
votes
1
answer
844
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 ...
6
votes
1
answer
1k
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 ...
- 345
0
votes
2
answers
307
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?
- 215
2
votes
1
answer
361
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?
- 529
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-...
- 1
4
votes
2
answers
621
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 ...
- 283
1
vote
1
answer
875
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 ...
- 175
1
vote
1
answer
759
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 ...
- 301
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 ...
- 73
2
votes
1
answer
209
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 ...
- 175
2
votes
1
answer
669
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 ...
- 23
3
votes
0
answers
135
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 ...
- 141
0
votes
1
answer
546
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 ...
0
votes
1
answer
120
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 ...
- 133
11
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 ...
- 1,682
5
votes
0
answers
423
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. ...
- 63
2
votes
1
answer
559
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 ...
- 23
4
votes
1
answer
222
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, ...
- 205
3
votes
1
answer
116
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.
...
- 125
5
votes
0
answers
208
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 ...
- 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
...
- 19.4k
1
vote
1
answer
210
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 ...
- 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, ...
- 5,382
3
votes
0
answers
192
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 ...
- 743
1
vote
1
answer
89
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 ...
- 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 ...
- 2,181
-2
votes
2
answers
1k
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?
- 2,181
2
votes
2
answers
563
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 ...
- 272
3
votes
2
answers
426
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 ...
- 579