# Tag Info

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 ...
• 12k
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 ...
• 12.5k
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 ...
• 277k
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 ...
• 81.8k

### 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.
• 1,623

### 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 ...

### 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: ...
• 277k
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 ...
• 277k
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 ...
• 30.8k
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" ...
• 30.8k

### 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 ...
• 549

### 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.
• 277k

### 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 ..."). ...
• 30.8k

### 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.
• 7,455

### 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.
• 72.5k
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 ...
• 1,623

### 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 ...
• 14k
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 ...
• 1,526
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 ...
• 277k