9
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ See this question: Is the Chomsky-hierarchy outdated? $\endgroup$ – Kaveh Jan 27 '11 at 5:18
  • $\begingroup$ Could you elaborate how the linked question relates, Kaveh? (Because I don't think its tone is helpful here, but individual answers might be) $\endgroup$ – Raphael Jan 27 '11 at 8:15
  • 2
    $\begingroup$ @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) $\endgroup$ – Tsuyoshi Ito Jan 27 '11 at 10:22
  • 2
    $\begingroup$ (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. $\endgroup$ – Tsuyoshi Ito Jan 27 '11 at 10:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 27 '11 at 14:18
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Jan 27 '11 at 9:56
  • 2
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Jan 27 '11 at 10:19
  • $\begingroup$ 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. $\endgroup$ – Kaveh Jan 27 '11 at 10:25
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Jan 27 '11 at 13:33
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 27 '11 at 14:22
  • $\begingroup$ @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. $\endgroup$ – Kaveh Jan 27 '11 at 15:26
  • $\begingroup$ 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. $\endgroup$ – Raphael Jan 27 '11 at 17:04
  • 1
    $\begingroup$ @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. :) $\endgroup$ – Kaveh Jan 27 '11 at 17:45
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Since LBAs are equivalent to the quite natural class of context-sensitive grammars, I don't think they were invented just for fun. ;) $\endgroup$ – Raphael Jan 27 '11 at 16:58
  • $\begingroup$ @Raphael: Yuval didn't imply that at all. $\endgroup$ – reinierpost Apr 1 '11 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.