<p>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!</p>

<p><strong>Reason 0</strong>: It is still <em>correct</em> in the sense that its definitions and results are not contradictory to newer knowledge.</p>

<p><strong>Reason 1</strong>: 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.</p>

<p><strong>Reason 2</strong>: 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 <em>are</em> simple and well-studied.</p>

<p><strong>Anti-Reason 3</strong>: Results do not <em>outdate</em> 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.</p>

CC BY-SA 3.0
2015-04-27T13:44:42.580Z
Don't you mean "NPDA" instead of "DPDA"?  Some context-free languages are recognized only by nondeterministic push-down automata.
Zsbán Ambrus
CC BY-SA 3.0
2015-04-27T14:20:12.723Z
@ZsbánAmbrus Quite right; I should have written just "PDA". Thanks!
Raphael
CC BY-SA 3.0
2015-04-27T17:35:33.653Z
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.
Sasho Nikolov
CC BY-SA 2.5
2010-10-19T13:50:44.620Z
"Mathematics does not become *old*, it becomes *classic*." (I don't know who this quote is attributed to, unfortunately.)
Heinrich Apfelmus
CC BY-SA 3.0
2010-10-19T06:48:35.720Z
2015-04-27T14:20:25.127Z
2015-04-27T14:20:25.127Z
Raphael
<p>In short: yes.</p>

<p>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.</p>

<p>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). </p>

CC BY-SA 2.5
2010-10-19T06:50:22.970Z
We found better names, yes. That does not imply that the results are outdated.
Raphael
CC BY-SA 2.5
2010-10-20T08:32:17.540Z
@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.
wren romano
CC BY-SA 2.5
2010-10-18T00:06:47.857Z
2010-10-18T00:06:47.857Z
wren romano
<p>If <i>anything</i> 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.</p>

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

CC BY-SA 2.5
2010-10-19T01:39:48.437Z
As Juris Hartmanis once shouted: **"What about Chomsky classes?? Chomsky classes are an abomination!!"**
Ryan Williams
CC BY-SA 2.5
2010-10-19T03:28:48.977Z
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
Scott Aaronson
CC BY-SA 2.5
2010-10-20T10:58:08.037Z
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: http://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.
Jakob
CC BY-SA 2.5
2010-10-20T13:08:15.947Z
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!
Raphael
CC BY-SA 2.5
2010-10-19T01:17:48.723Z
2010-10-19T01:17:48.723Z
Scott Aaronson
<p>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.</p>

<p>The following illustration might be helpful:</p>

<p><img src="https://www.willamette.edu/~fruehr/446/figs/hierarchy.JPG" /></p>

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

CC BY-SA 2.5
2010-10-17T18:44:22.793Z
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.
Sadeq Dousti
CC BY-SA 2.5
2010-10-17T20:30:17.423Z
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?
Jakob
CC BY-SA 2.5
2010-10-17T20:50:56.300Z
I don't think it is a bad idea, though one must find some application for which the new extension fits.
Sadeq Dousti
CC BY-SA 2.5
2010-10-17T13:19:53.717Z
2010-10-17T13:30:14.673Z
2017-03-09T18:04:14.373Z
Sadeq Dousti
<p>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.</p>

<p>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).</p>

CC BY-SA 4.0
2018-12-04T12:01:56.430Z
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.]
DG_
CC BY-SA 2.5
2010-11-09T16:59:29.507Z
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.
mgalle
CC BY-SA 2.5
2010-11-09T13:10:51.183Z
2010-11-09T13:10:51.183Z
mgalle
<p>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 <a href="http://www.math.ucdavis.edu/~greg/zoology/relations.html">Complexity Zoo Diagram</a>. Does the hierarchy play any role in current research anymore? I found only little references to Chomsky here at cstheory.stackexchange, and in <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo">Complexity Zoo</a> the names Chomsky and Schützenberger are not mentioned at all.</p>

<p>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:</p>

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

<p>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.</p>

<p>I found on GCSL and VPL:</p>

<ul>
<li>Robert McNaughton: An Insertion into the Chomsky Hierarchy?. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa. S. 204-212, 1999</li>
<li><a href="http://en.wikipedia.org/wiki/Nested_word#References">http://en.wikipedia.org/wiki/Nested_word#References</a> (VPL)</li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2011-04-01T16:55:09.137Z
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.
reinierpost
CC BY-SA 2.5
2010-10-17T19:37:52.727Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-17T20:20:16.523Z
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.
Jakob
CC BY-SA 2.5
2010-10-20T08:34:21.097Z
You can also add star-free languages strictly below regular languages. They're like regular, but without the Kleene star. Well known. Well behaved.
wren romano
CC BY-SA 2.5
2010-11-12T16:14:17.007Z
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.
Jakob
<cc.complexity-theory><automata-theory><fl.formal-languages><big-picture><teaching>
Is the Chomsky-hierarchy outdated?
Jakob
# Is the Chomsky-hierarchy outdated?

(Asked by: username_0 on 2010-10-17)

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](http://www.math.ucdavis.edu/~greg/zoology/relations.html). 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](http://qwiki.stanford.edu/wiki/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:

* Robert McNaughton: An Insertion into the Chomsky Hierarchy?. In: Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa. S. 204-212, 1999
* <http://en.wikipedia.org/wiki/Nested_word#References> (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.

**Tags:** cc.complexity-theory, automata-theory, fl.formal-languages, big-picture, teaching

> **Comments:**
> **username_2**: 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.  
> **username_0**: 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.  
> **username_3**: You can also add star-free languages strictly below regular languages. They're like regular, but without the Kleene star. Well known. Well behaved.  
> **username_0**: 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 username_11's answer because he has least reputation so far.  
> **username_1**: 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.  

---

## 5 answers

### Answer by username_11 on 2010-11-09. Score: 23 | Accepted answer

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

> **Comments:**
> **username_11**: 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.  
> **username_12**: 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.]  

---

### Answer by username_3 on 2010-10-18. Score: 28

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

> **Comments:**
> **username_4**: We found better names, yes. That does not imply that the results are outdated.  
> **username_3**: @username_4: 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.  

---

### Answer by username_8 on 2010-10-19. Score: 25

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.

> **Comments:**
> **username_9**: As Juris Hartmanis once shouted: **"What about Chomsky classes?? Chomsky classes are an abomination!!"**  
> **username_8**: 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  
> **username_0**: 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: http://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.  
> **username_4**: 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!  

---

### Answer by username_4 on 2010-10-19. Score: 21

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.

> **Comments:**
> **username_7**: "Mathematics does not become *old*, it becomes *classic*." (I don't know who this quote is attributed to, unfortunately.)  
> **username_5**: Don't you mean "NPDA" instead of "DPDA"?  Some context-free languages are recognized only by nondeterministic push-down automata.  
> **username_4**: @ZsbánAmbrus Quite right; I should have written just "PDA". Thanks!  
> **username_6**: 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.  

---

### Answer by username_10 on 2010-10-17. Score: 11

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:

![](https://www.willamette.edu/~fruehr/446/figs/hierarchy.JPG)

**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).

> **Comments:**
> **username_10**: 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.  
> **username_0**: 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?  
> **username_10**: I don't think it is a bad idea, though one must find some application for which the new extension fits.  

---

