50
$\begingroup$

The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the full Complexity Zoo Diagram. Does the hierarchy play any role in current research anymore? I found only little references to Chomsky here at cstheory.stackexchange, and in Complexity Zoo the names Chomsky and Schützenberger are not mentioned at all.

Is current research more focused on other means of description but formal grammars? I was looking for practical methods to describe formal languages with different expressiveness, and stumbled upon growing context sensitive language (GCSL) and visibly pushdown languages (VPL), which both lie between the classic Chomsky languages. Shouldn't the Chomsky hierarchy be updated to include them? Or is there no use of selecting a specific hierarchy from the full set of complexity classes? I tried to select only those languages that can be fit in gaps of the Chomsky hierarchy, as far as I understand:

REG (=Chomsky 3) ⊊ VPL ⊊ DCFL ⊊ CFL (=Chomsky 2) ⊊ GCSL ⊊ CSL (=Chomsky 1) ⊊ R ⊊ RE

I still don't get where "mildly context-sensitive languages" and "indexed languages" fit in (somewhere between CFL and CSL) although there seems to be of practical relevance for natural language processing (but maybe anything of practical relevance is less interesting in theoretical research ;-). In addition you could mention GCSL ⊊ P ⊂ NP ⊂ PSPACE and CSL ⊊ PSPACE ⊊ R to show the relation to the famous classes P and NP.

I found on GCSL and VPL:

I'd also be happy if you know any more recent textbook on formal grammars that also deal with VPL, DCLF, GCSL and indexed grammars, preferable with pointers to practical applications.

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ A minor point: I do not view the absence of the names Chomsky and Schützenberger in the Complexity Zoo as an evidence that “the Chomsky hierarchy is outdated.” The Chomsky hierarchy is a notion in the formal language theory. The Complexity Zoo is a website primarily about the complexity theory, although it contains some notions in the formal language theory such as context-free languages. They are related but distinct fields. It would be outdated if it were not mentioned in a textbook in the formal language theory, but I do not know if that is the case. $\endgroup$
    – Tsuyoshi Ito
    Oct 17, 2010 at 19:37
  • 7
    $\begingroup$ Good point, Tsuyoshi. Frankly, I'd like to see a "Formal Languages Zoo" with good theoretical grounding (references to research papers!) but also practical resources. For instance there are dozens of syntax variants of Backus-Naur-Form, and variants of Regular Expressions (some of them even not regular). Beside the simple Chomsky-hierarchy I found it difficult to get a clear picture of the current state of research in formal languages. $\endgroup$
    – Jakob
    Oct 17, 2010 at 20:20
  • $\begingroup$ You can also add star-free languages strictly below regular languages. They're like regular, but without the Kleene star. Well known. Well behaved. $\endgroup$
    – wren romano
    Oct 20, 2010 at 8:34
  • 1
    $\begingroup$ As several answers showed me, formal grammars à la Chomsky are a historic method to describe formal languages, that has reached its limits. I am still looking for a good overviews of formal grammars, that are not focused on complexity theory, but thanks for all the further references! I'll accept mgalle's answer because he has least reputation so far. $\endgroup$
    – Jakob
    Nov 12, 2010 at 16:14
  • 2
    $\begingroup$ In computer science, computer language design, software design and programming, context-free grammars and languages and regular expressions and languages are basic working equipment and as important as ever. But for arbitrary grammars, LBAs and context-sensitive languages, on the other hand, I have seen few applications or none at all. $\endgroup$
    – reinierpost
    Apr 1, 2011 at 16:55

5 Answers 5

Reset to default
22
$\begingroup$

From what I have seen in the Natural Language Processing community, formal grammars à la Chomsky are not used so much any more. They (too) think that the Chomsky Hierarchy is outdated to model language.

What took its place is stuff like Re-writting rule (the Lars algorithm), dependency models (Dan Klein), Tree Substitution Grammar (the DOP model), Binary Feature Grammars (Alex Clark).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Re-reading my answer, it sounds more negative than I wanted it too sound. RL and CFL were never supposed to be realistics models of natural language, and most of the "new" models are actually inspired in them. $\endgroup$
    – mgalle
    Nov 9, 2010 at 16:59
  • $\begingroup$ I thought that RL weren't even designed as a model of natural languages, but as a model of some system behaviour. [Kleene's original text doesn't use the formal language terminology either.] $\endgroup$
    – DG_
    Dec 4, 2018 at 12:01
28
$\begingroup$

In short: yes.

More particularly: Chomsky was one of the first to formalize a hierarchy relating languages, grammars, and automata. This insight is still very relevant and is taught in all intro courses on automata theory. However, the specific hierarchy Chomsky came up with and the names for the elements of the hierarchy aren't really significant anymore. We've since invented numerous formalisms which fall between levels of Chomsky's hierarchy, above it, or below it. And the names Chomsky used aren't particularly interesting, i.e. they aren't based on an interesting measure of complexity or anything, they're just numbers. Should mildly context sensitive languages be Type-1.5 or Type-1.7 or Type-1.3? Who cares. "Mildly context sensitive" is a much more informative name.

The Complexity Zoo is a bit different because it's full of all sorts of conditional equivalences and the like. A more modern hierarchy for automata theory wouldn't be linear (e.g., compare CFG vs PEG) but it would still have a well-known topology. To get a perspective on modern automata theory you should look at work on parser combinator libraries and some of the stuff on unification and type theory (though those both branch out far afield).

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ We found better names, yes. That does not imply that the results are outdated. $\endgroup$
    – Raphael
    Oct 19, 2010 at 6:50
  • 4
    $\begingroup$ @Raphael: The outdatedness isn't because of the names, per se, it's because the specific hierarchy introduced by Chomsky is not used any more. The inclusions described by the Chomsky hierarchy are (a) still correct, and (b) among the inclusions in any modern hierarchy; but the Chomsky hierarchy as such, is not terribly relevant excepting that it happens to hit some of the well-known high points. People don't do research on the Chomsky hierarchy any more, they do research elsewhere. This isn't like the polynomial tower which has reasons for its names/structures. $\endgroup$
    – wren romano
    Oct 20, 2010 at 8:32
25
$\begingroup$

If anything in TCS is outdated, it's this inclusion hierarchy of the tiny subset of complexity classes that happened to be known / considered interesting in 1956.

Rest in peace, Chomsky Hierarchy, and may you haunt the undergrad theory curriculum no more.

Improve this answer
$\endgroup$
4
  • 13
    $\begingroup$ As Juris Hartmanis once shouted: "What about Chomsky classes?? Chomsky classes are an abomination!!" $\endgroup$
    – Ryan Williams
    Oct 19, 2010 at 1:39
  • 1
    $\begingroup$ Ryan: I also remember Juris calling the CH an "abomination"! As I wrote my answer, I was debating whether he'd want his remark made public. But you know him better than I do... :-D $\endgroup$
    – Scott Aaronson
    Oct 19, 2010 at 3:28
  • $\begingroup$ This comment may also be motivated at least a tiny bit by the pejorative view of some theoretical computer sciences and mathematicians to linguistics and other "weak" sciences: xkcd.com/435. But sure the Chomsky hierarchy today obscures the view to modern complexity theory, so this answers my question. Still it would be nice to have some updated replacement to start with in the undergrad theory curriculum, especially if you are more interested in formal languages and grammars for practical applications. $\endgroup$
    – Jakob
    Oct 20, 2010 at 10:58
  • 3
    $\begingroup$ The Chomsky Hierarchy lists classes of languages ordered by complexity of description, not complexity of computation that is usually implied when you use the term "complexity theory". They are related, obviously. Anyway, I still fail to see how one (rough) hierachy can obscure more refined classes that can hardly be understood without having come from Chomsky Hierarchy. They are the entrance door! $\endgroup$
    – Raphael
    Oct 20, 2010 at 13:08
21
$\begingroup$

If you consider Chomsky's Hierarchy with "modern" names (i.e. REG, LIN, CFL, CSL, RE resp. DFA/NFA, PDA, LBA, TM), I say: No, it is not outdated!

Reason 0: It is still correct in the sense that its definitions and results are not contradictory to newer knowledge.

Reason 1: These classes/computation models are still the first you teach -- because they are simple and well studied. Try teaching LR automaton to an undergrad without covering DFA/DPDA first.

Reason 2: The classes are still the first/major benchmarks for new inventions (I skimmed a paper about multi-CFGs which, of course, said: more than CFG, less than CSG). That may be partly because they are taught first, but also because they are simple and well-studied.

Anti-Reason 3: Results do not outdate just because new classes/models have been found. They keep their value as basics of the field despite them not being used on the research frontier actively.

Improve this answer
$\endgroup$
4
  • 10
    $\begingroup$ "Mathematics does not become old, it becomes classic." (I don't know who this quote is attributed to, unfortunately.) $\endgroup$
    – Heinrich Apfelmus
    Oct 19, 2010 at 13:50
  • $\begingroup$ Don't you mean "NPDA" instead of "DPDA"? Some context-free languages are recognized only by nondeterministic push-down automata. $\endgroup$
    – Zsbán Ambrus
    Apr 27, 2015 at 13:44
  • $\begingroup$ @ZsbánAmbrus Quite right; I should have written just "PDA". Thanks! $\endgroup$
    – Raphael
    Apr 27, 2015 at 14:20
  • $\begingroup$ The last reason is not convincing at all (I guess that's why it's an anti reason?). Plenty of results get outdated because they are subsumed or sometimes even trivialized by a different approach to the subject. I am not saying this the case here, just that the reason as stated does not say much. Also, a grammatical nitpick: "outdate" is not a verb. $\endgroup$
    – Sasho Nikolov
    Apr 27, 2015 at 17:35
11
$\begingroup$

I think it depends on the model of computation. If you consider the finite/pushdown/etc. automata as a model of computation, then Chomsky hierarchy becomes important (see for instance Sipser's book). On the other hand, it plays little role in the Turing model of computation.

The following illustration might be helpful:

Edit: Formal languages play an important role in designing computer languages (such as Java) and compilers, as well as in the natural-language processing (NLP).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry András, I can't understand your comment. The OP asked if Chomsky hierarchy is outdated. His reasoning was that he didn't see it in complexity zoo, etc. I answered that if he considers automata as a model of computing, the Chomsky hierarchy becomes relevant. In addition, I mentioned that classes of this hierarchy are important to compiler design and NLP algorithms. IMHO, that is totally related to the question. $\endgroup$
    – Sadeq Dousti
    Oct 17, 2010 at 18:44
  • 2
    $\begingroup$ Sure the Chomsky hierarchy is not really outdated, it is found in most introductions of theoretical computer science, formal languages, compiler design etc. But beside this, there seems to be nothing new to tell. I think thank languages between REG and CFL, and between CFL, may be of importance as well. Is it just a bad idea to extend the hierarchy with these languages because Chomsky hierarchy has a smell of "outdated" as not important for current research? $\endgroup$
    – Jakob
    Oct 17, 2010 at 20:30
  • $\begingroup$ I don't think it is a bad idea, though one must find some application for which the new extension fits. $\endgroup$
    – Sadeq Dousti
    Oct 17, 2010 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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