Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
22 votes
Accepted

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

The linear bounded Turing machine is restricted to a tape whose length is a linear function of the length of the input. If the length limit were a constant, then the machine would be no more powerful ...
rici's user avatar
  • 12k
6 votes
Accepted

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

A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA. What happens if only one of the two stacks is linear bounded and the other is unlimited? I optimistically wrote a quick ...
Vor's user avatar
  • 12.5k
6 votes
Accepted

Is every language in PTime also context-sensitive?

It is an open question to separate $\mathsf{L}$ (that is, $\mathsf{DSPACE}(\log n)$) and $\mathsf{P}$ (what you call PTime), so in particular we have no example of a polytime language which requires ...
Yuval Filmus's user avatar
6 votes
Accepted

Is it possible to convert LBA into DFA?

No, you can't do this. A single LBA can process inputs of any possible finite length. For any individual input, there are only finitely many possible tape configurations but, over all possible inputs ...
David Richerby's user avatar
4 votes

Are Linear Bounded Automatons Turing Complete?

A linear bounded automaton is a Turing machine that runs on input of size $n$ in $\mathcal{O}(n)$ space. By the space hierachy theorem there exist languages that need e.g. $\omega(n^2)$ space.
ttnick's user avatar
  • 1,623
4 votes

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

I think we must first understand the description of a machine and the input size, so that the comparison is of only valid objects. Let say N is a input size. This means machines will have these ...
Devendra Bhave's user avatar
3 votes

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

The LBA maintains a counter $c$, initialized by $1$, which is stored on a parallel track. It thinks of the rest of the tape as an integer $m$. It then repeatedly executes the following instructions: ...
Yuval Filmus's user avatar
3 votes
Accepted

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

For simplicity, let me assume that the only allowed rules are of the form $A \to aB$ and $A \to \epsilon$. Denote the set of nonterminals by $V$, where $S \in V$ is the starting symbol. Construct a ...
Yuval Filmus's user avatar
3 votes
Accepted

Restrictions to counter machines capturing LBA

Programs with natural numbers as data and as instructions increment, decrement and zero test are know as register machines or counter automata. (Wikipedia cites several sources, usually I refer to ...
Hendrik Jan's user avatar
  • 30.8k
3 votes
Accepted

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

It seems the author of the book is a little careless at this point. His definition of context-sensitive is that "the right-hand side of a rule must never be shorter than the left-hand side" ...
Hendrik Jan's user avatar
  • 30.8k
2 votes

Why is the halting problem decidable for LBA?

In short, A LBA has finite number of configurations, say D. Hence, we can run for D steps and conclude the result. If it runs for more that D steps, by pigeonhole principle, we can say that, it is ...
SiluPanda's user avatar
  • 549
2 votes

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

Repeatedly remove an $a$ from the beginning and a $bb$ from the end until the string becomes empty. If you cannot do it at any point, reject, otherwise, accept.
Yuval Filmus's user avatar
2 votes

Is it possible to convert LBA into DFA?

Yes, you just modelled the LBA by a finite state device. You have to decide what are the actions of that model, probably the instructions of the LBA ("in state $q$ on reading $a$ on the tape do ..."). ...
Hendrik Jan's user avatar
  • 30.8k
2 votes

Reduce undecidable language to decidable language?

... but then $A_{\mathrm{TM}}$ would be decidable! No. Because your $f$ is not computable since one cannot compute whether $M$ accepts $w$, as Yuval Filmus said in the comment.
xskxzr's user avatar
  • 7,455
2 votes

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

It's famously unknown whether deterministic and non-deterministic LBA accept the same set of languages.
Raphael's user avatar
  • 72.5k
2 votes
Accepted

Number of Configurations of LBA(Linear Bounded Automaton)

If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the ...
ttnick's user avatar
  • 1,623
2 votes

Are Linear Bounded Automatons Turing Complete?

You know that Turing machines can accept languages that aren't recursive. A linear bounded automaton (LBA) running on word $\omega$ has a finite tape at it's disposal, so the total number of ...
vonbrand's user avatar
  • 14k
2 votes
Accepted

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

Welcome to CS.SE! I only know of the latter definition, i.e. the one allowing $S \to \varepsilon$ but disallowing $S$ in the right sides of productions. Ultimately this is done to have a nice ...
Watercrystal's user avatar
  • 1,526
2 votes
Accepted

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

The conversion from nondeterministic Turing machine to deterministic Turing machines doesn't conserve space. The best known construction, known as Savitch's theorem, converts a nondeterministic Turing ...
Yuval Filmus's user avatar
2 votes

Difference between linear bound automata and a Turing machine

Notice that linear bounded automata are precisely all TM's who use $O(n)$ space. Now, by the space-hierarchy theorem, for any $f$ where $n=o(f)$ (for an extreme example, $f(n)=2^n$) we would have $...
nir shahar's user avatar
  • 11.6k
2 votes

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

A right linear grammar with rules of the form $A\to aB$ and $A\to\varepsilon$ is a finite state automaton in disguise. Such a linear grammar is ambiguous iff the following holds: There is a pair of ...
Hendrik Jan's user avatar
  • 30.8k
2 votes
Accepted

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

I suspect the word "finite" is confusing you. Every integer is "finite", yet the set of all possible integers is not finite, and there is no finite number that is an upper bound ...
D.W.'s user avatar
  • 160k
1 vote

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

Given a Turing machine $M$, you can construct an LBA $A$ that given as input a word of length $n$, it simulates $M$ on the empty tape as long as $M$ uses up to $n$ space, and the moment $M$ exceeds ...
Yuval Filmus's user avatar
1 vote

Is it decidable whether a TM is a LBA?

An LBA is limited to working only on the space defined by the input. That means it won't ever move right on reading a blank space (if your model doesn't allow writing blank, only a fake blank, that is)...
vonbrand's user avatar
  • 14k
1 vote
Accepted

Does a type-1 automaton always have to terminate?

Pushdown automata do not necessarily halt. They are not forced to read input each step, they can also do so-called $\lambda$-instructions where the tape is not advanced. Then we can have an infinite ...
Hendrik Jan's user avatar
  • 30.8k
1 vote
Accepted

Undecidability of emptiness of LBA

Given a Turing machine $M$, we can construct an LBA $B$ which on input of length $n$ checks whether $M$ halts on the empty input within $n$ space. Therefore $L(B)$ is empty iff $M$ doesn't halt.
Yuval Filmus's user avatar
1 vote
Accepted

A confusion about the Reduction via Computation History

It seems you confused two things What computation history is and How the hypothetical decider $R$ and LBA $B$ are used to decide $A_{TM}$ You can think of TM configuration as snapshot of the tape ...
fade2black's user avatar
  • 9,837
1 vote
Accepted

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

As I understand, you are asking two questions. Let me address them separately: You don't. Your assumption on $M$ did not require anything more than $L(M) = A$, which is too weak for such a proof. ...
dkaeae's user avatar
  • 5,027
1 vote
Accepted

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

Thanks to @YuvalFilmus I managed to reduce the Halting problem to the given problem. We design an LBA B, that given an instance of the Halting problem, $\langle M,x\rangle$, accepts the valid ...
Arka Pal's user avatar
  • 311
1 vote

Reduce undecidable language to decidable language?

If a language $B$ is decidable, there is an algorithm that computes it. If a language $A$ is mapping-reducible to $B$, then you have the following algorithm for $A$: first compute ...
David Richerby's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible