<p>It seems that not just CSG but also CFG, ... are out of fashion these days. I think these days automata and PDA are usually thought in computability/complexity theory courses (if at all) and there they are included <em>not</em> for their own sake but to introduce Turing Machines. </p>

<p>Grammars are probably interesting for compiler theory but not so much for computability/complexity to be included in an introductionary undergrad course. There are too many topics that one would like to cover but a one semester course is just too short and we have to select and many of these topics which we cannot cover because of time restrictions are way more interesting than LBA.</p>

CC BY-SA 2.5
2011-01-27T13:33:12.757Z
I wish you were universally true!  The intro class on TCS taught in my univ is half automata/CFL.  I'm TA-ing this class, and the students seem really far from being interested.  This may be another reason why CFL/CSL are no longer presented: there are topics which are way more exciting.
Michaël Cadilhac
CC BY-SA 2.5
2011-01-27T14:22:24.703Z
Well, CS theory is not only complexity. In particular CFG as well as related automaton models are very important (at least as foundations) in many branches of CS. An introductory course should prepare you for all branches. Sorry, but this answer smells like ignorance. Also, it does not answer the question.
Raphael
CC BY-SA 2.5
2011-01-27T15:26:49.277Z
@Raphael, I am talking about *computability/complexity* theory courses which is where automata theory is being thought in universities I know right now. No one said anything about theory courses in general. I think you should read posts carefully before accusing others of ignorance. My post does answer the question: why LBA is not thought in computability/complexity theory courses? That is the reason, and that is the reason why computability and complexity theory textbooks don't include much about LBA, whether you like it or not.
Kaveh
CC BY-SA 2.5
2011-01-27T17:04:15.220Z
So you are private to the personal reasons of every author and lecturer in the whole world? Yea, right. Anyway, please note that the word "complexity" does not occur in the posted question at all. Note also that by theprise's comment above and edit, you did not answer the question. Fact, wether you like it or not.
Raphael
CC BY-SA 2.5
2011-01-27T17:45:56.320Z
@Raphael, you still don't read carefully and continue to interpret what I write the way you prefer, it seems to me that you just want to argue, I think my point is clear enough, therefore feel free to think as you like. :)
Kaveh
CC BY-SA 2.5
2011-01-27T10:16:00.333Z
2011-01-27T10:28:49.823Z
2011-01-27T10:28:49.823Z
Kaveh
<p>Well, ask your professor why he did it. I can only guess.</p>

<p>They are not as interesting as Turing complete models and PDA because they are in the void of uselessness* they share, of course, with their language equivalent: not as powerful as possible, but already very much intractable.</p>

<p>Another reason might be that not as much is known (guessing here) about them, but that might come down to a chicken-egg-problem.</p>

<p>It is unclear weather $NLBA = DLBA$, so that might pose problems for didactics. Also, typical proofs (e.g. accepted language, model equivalences) are much harder than for other models.</p>

<p>(*) deliberate exaggeration</p>

CC BY-SA 2.5
2011-01-27T08:22:10.647Z
2011-01-27T08:22:10.647Z
Raphael
<p>Regular expressions and CFGs are used in practice for parsing code (that is, programming languages). The reason is that there are very efficient algorithms for parsing them. LBAs, on the other hand, are too powerful to actually use in that context.</p>

<p>One historical origin of automata theory is the subject of compiler construction. For the reason mentioned above, only regular languages and CFGs are useful for constructing compilers (notwithstanding the fact that attributive grammars are not really CFGs, and that CFG parsing algorithms don't really parse the entire class of CFGs). LBAs might have been invented by Chomsky as some intermediate level of complexity between the mundane and "English". So perhaps the proper place to teach them is in linguistics courses rather than computer science ones!</p>

CC BY-SA 2.5
2011-04-01T16:59:32.317Z
@Raphael: Yuval didn't imply that at all.
reinierpost
CC BY-SA 2.5
2011-01-27T16:58:52.543Z
Since LBAs are equivalent to the quite natural class of context-sensitive grammars, I don't think they were invented just for fun. ;)
Raphael
CC BY-SA 2.5
2011-01-27T16:40:18.253Z
2011-01-27T16:40:18.253Z
Yuval Filmus
<p>With "appropriate" modifications we can turn these classes into complexity classes; Finite Automata into $NC^1$, CFL into LogCFL, and LBA into PSPACE. </p>

<p>It should now be quite clear why we are interested in the first two more than LBA. The first two naturally fit into the usual definition of feasible computation. But PSPACE does not.</p>

CC BY-SA 2.5
2011-01-27T09:56:37.403Z
turning an LBA into PSPACE sounds almost like linear space is all you need to capture PSPACE which clearly can't be true. So what's my error in thinking ?
Suresh Venkat
CC BY-SA 2.5
2011-01-27T10:19:12.333Z
@Suresh: There are the following connections.  The class of problems that are (NC1-)reducible to regular languages is NC1, the class of problems (log-space-)reducible to CFL is LogCFL, and the class of problems (NC1- or log-space-)reducible to LBA is PSPACE.  I am not sure if we can use the same notion of reducibility in all these three cases.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T10:25:11.540Z
Containing a complete problem for another class (even under $AC^0$ reductions) does not seem to be a good reason for the class being interesting.
Kaveh
CC BY-SA 2.5
2011-01-27T09:51:15.710Z
2011-01-27T09:51:15.710Z
V Vinay
<p>In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, although finite and pushdown automata receive a lot of attention. Surely there must be a good reason for why LBAs are given less focus than their counterparts?</p>

CC BY-SA 2.5
2011-01-27T05:18:37.413Z
See this question: [Is the Chomsky-hierarchy outdated?](http://cstheory.stackexchange.com/questions/2252/is-the-chomsky-hierarchy-outdated)
Kaveh
CC BY-SA 2.5
2011-01-27T08:15:37.037Z
Could you elaborate how the linked question relates, Kaveh? (Because I don't think its tone is helpful here, but individual answers might be)
Raphael
CC BY-SA 2.5
2011-01-27T10:22:04.950Z
@Raphael: The answers to the question Kaveh linked to explain why context-sensitive languages are not considered as important as were before: in short, there are other, more interesting models to consider.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T10:22:55.057Z
(cont’d)  The same reason applies to “linear bounded automata.”  It is funny that I had never heard of that name.  To me they are just O(n)-space deterministic/nondeterministic Turing machines, and I cannot see why we should single out O(n)-space ones (instead of polynomial space or O(log n)-space or whatever), although there must have been a historic reason.  In addition, neither the class DSPACE(O(n)) nor NSPACE(O(n)) is [closed under subroutine calls](http://cstheory.stackexchange.com/questions/3439/why-do-we-consider-log-space-as-a-model-of-efficient-computation-instead-of-poly/3448#3448).
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T14:18:45.753Z
Tsuyoshi, my interpretation of the question is that FA, PDA and the rest of the Chomsky Hierarchy (by your/the answers' reasoning equally boring) are taught, but LBA aren't.
Raphael
CC BY-SA 2.5
2011-01-27T14:40:51.197Z
@Raphael, your interpretation of the question is what I was going for, I edited the question to try to clarify.
goric
<computability><fl.formal-languages><automata-theory>
Why are linear bounded automata not as popular as other automata?
goric
# Why are linear bounded automata not as popular as other automata?

(Asked by: username_0 on 2011-01-27)

In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, although finite and pushdown automata receive a lot of attention. Surely there must be a good reason for why LBAs are given less focus than their counterparts?

**Tags:** computability, fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: See this question: [Is the Chomsky-hierarchy outdated?](http://cstheory.stackexchange.com/questions/2252/is-the-chomsky-hierarchy-outdated)  
> **username_2**: Could you elaborate how the linked question relates, Kaveh? (Because I don't think its tone is helpful here, but individual answers might be)  
> **username_3**: @Raphael: The answers to the question Kaveh linked to explain why context-sensitive languages are not considered as important as were before: in short, there are other, more interesting models to consider.  (more)  
> **username_3**: (cont’d)  The same reason applies to “linear bounded automata.”  It is funny that I had never heard of that name.  To me they are just O(n)-space deterministic/nondeterministic Turing machines, and I cannot see why we should single out O(n)-space ones (instead of polynomial space or O(log n)-space or whatever), although there must have been a historic reason.  In addition, neither the class DSPACE(O(n)) nor NSPACE(O(n)) is [closed under subroutine calls](http://cstheory.stackexchange.com/questions/3439/why-do-we-consider-log-space-as-a-model-of-efficient-computation-instead-of-poly/3448#3448).  
> **username_2**: Tsuyoshi, my interpretation of the question is that FA, PDA and the rest of the Chomsky Hierarchy (by your/the answers' reasoning equally boring) are taught, but LBA aren't.  
> **username_0**: @Raphael, your interpretation of the question is what I was going for, I edited the question to try to clarify.  

---

## 4 answers

### Answer by username_7 on 2011-01-27. Score: 13 | Accepted answer

With "appropriate" modifications we can turn these classes into complexity classes; Finite Automata into $NC^1$, CFL into LogCFL, and LBA into PSPACE.

It should now be quite clear why we are interested in the first two more than LBA. The first two naturally fit into the usual definition of feasible computation. But PSPACE does not.

> **Comments:**
> **username_8**: turning an LBA into PSPACE sounds almost like linear space is all you need to capture PSPACE which clearly can't be true. So what's my error in thinking ?  
> **username_3**: @Suresh: There are the following connections.  The class of problems that are (NC1-)reducible to regular languages is NC1, the class of problems (log-space-)reducible to CFL is LogCFL, and the class of problems (NC1- or log-space-)reducible to LBA is PSPACE.  I am not sure if we can use the same notion of reducibility in all these three cases.  
> **username_1**: Containing a complete problem for another class (even under $AC^0$ reductions) does not seem to be a good reason for the class being interesting.  

---

### Answer by username_1 on 2011-01-27. Score: 3

It seems that not just CSG but also CFG, ... are out of fashion these days. I think these days automata and PDA are usually thought in computability/complexity theory courses (if at all) and there they are included *not* for their own sake but to introduce Turing Machines.

Grammars are probably interesting for compiler theory but not so much for computability/complexity to be included in an introductionary undergrad course. There are too many topics that one would like to cover but a one semester course is just too short and we have to select and many of these topics which we cannot cover because of time restrictions are way more interesting than LBA.

> **Comments:**
> **username_4**: I wish you were universally true!  The intro class on TCS taught in my univ is half automata/CFL.  I'm TA-ing this class, and the students seem really far from being interested.  This may be another reason why CFL/CSL are no longer presented: there are topics which are way more exciting.  
> **username_2**: Well, CS theory is not only complexity. In particular CFG as well as related automaton models are very important (at least as foundations) in many branches of CS. An introductory course should prepare you for all branches. Sorry, but this answer smells like ignorance. Also, it does not answer the question.  
> **username_1**: @Raphael, I am talking about *computability/complexity* theory courses which is where automata theory is being thought in universities I know right now. No one said anything about theory courses in general. I think you should read posts carefully before accusing others of ignorance. My post does answer the question: why LBA is not thought in computability/complexity theory courses? That is the reason, and that is the reason why computability and complexity theory textbooks don't include much about LBA, whether you like it or not.  
> **username_2**: So you are private to the personal reasons of every author and lecturer in the whole world? Yea, right. Anyway, please note that the word "complexity" does not occur in the posted question at all. Note also that by theprise's comment above and edit, you did not answer the question. Fact, wether you like it or not.  
> **username_1**: @Raphael, you still don't read carefully and continue to interpret what I write the way you prefer, it seems to me that you just want to argue, I think my point is clear enough, therefore feel free to think as you like. :)  

---

### Answer by username_2 on 2011-01-27. Score: 3

Well, ask your professor why he did it. I can only guess.

They are not as interesting as Turing complete models and PDA because they are in the void of uselessness\* they share, of course, with their language equivalent: not as powerful as possible, but already very much intractable.

Another reason might be that not as much is known (guessing here) about them, but that might come down to a chicken-egg-problem.

It is unclear weather $NLBA = DLBA$, so that might pose problems for didactics. Also, typical proofs (e.g. accepted language, model equivalences) are much harder than for other models.

(\*) deliberate exaggeration


---

### Answer by username_5 on 2011-01-27. Score: 2

Regular expressions and CFGs are used in practice for parsing code (that is, programming languages). The reason is that there are very efficient algorithms for parsing them. LBAs, on the other hand, are too powerful to actually use in that context.

One historical origin of automata theory is the subject of compiler construction. For the reason mentioned above, only regular languages and CFGs are useful for constructing compilers (notwithstanding the fact that attributive grammars are not really CFGs, and that CFG parsing algorithms don't really parse the entire class of CFGs). LBAs might have been invented by Chomsky as some intermediate level of complexity between the mundane and "English". So perhaps the proper place to teach them is in linguistics courses rather than computer science ones!

> **Comments:**
> **username_2**: Since LBAs are equivalent to the quite natural class of context-sensitive grammars, I don't think they were invented just for fun. ;)  
> **username_6**: @Raphael: Yuval didn't imply that at all.  

---

