The Chomsky Hierarchy

CS Bits

This is first in a series of posts on various computer science topics that strike my fancy.

In spite of being a reasonably successful computer science academic, I’ve little to no formal computer science training. So, my background knowledge base is a bit eclectic. There’s a list of things that I presume is common knowledge amongst computer scientists. (I regularly quiz my students on these.)

One reason I think these topics should be common knowledge is because they are super cool. So they seem worth sharing.

The Chomsky Hierarchy

The Wikipedia article is perfectly fine from a technical point of view and for many bits is reasonable accessible. So, I commend it to you and won’t replicate that content per se.

Some key takeaways:

  • The correlative ideas of a formal grammar and formal language.
  • You should know what productions, terminals, and nonterminals are. You should know, at least roughly the (E)BNF syntax for grammars.
  • You should have a firm grip that a language is a set of (finite)?strings, that a (finite) grammar describes that set, and that we can have alternative grammars for the same languages.
  • You should know that languages can be, and typically are, infinite (in spite of being described by a finite grammar and containing only finite strings). You should know why and also which infinite cardinality.
  • You should understand the dual nature of grammars (i.e. that they can be used to generate recognizers and generators of languages).
  • You should understand the correspondence between a grammar and a class of machines for recognising elements of the language.
  • From the last, you should see a relation between the expressivity of a grammar and the complexity of recognising the language.
  • You should understand how and why the typical regexp package in programming languages are typical not formalisms for writing regular grammars.
  • You should grasp the containment aspect of the hierarchy.

And, of course, you should have a good concrete command of the material. E.g. you should be able to write a context free grammar that is expressible as a regular grammar and one which is not, among other things.

Why know all this

First, and probably most importantly, it’s a core part of computer science and one of its glories. Think Maxwell’s equations in physics. Regular and context free languages are the standard way of describing (most aspects) of programming language syntax and every computer scientist should have a basic grip on programming language theory.

Second, studying it gives you a great foundation for a number of skills, particularly in complexity theory. The kind of math you have to master the hierarchy (to any degree!) is a kind of math that’s pervasive in computer science. (Though its not the only key bit of math.)

Finally (for now), it’s great from a conceptual point of view. The very idea that we have languages described by grammars and recognized by machines is amazing and beautiful. It also very nicely models a more general pattern of trying to capture a phenomenon (e.g., a language) by a precise description (e.g., a grammar) that gives you both theoretical insight (e.g., complexity) and a means of computation (e.g., the corresponding machine). While there are limits to this methodology, it can take you a long way.

Personal notes

My first encounter of the Chomsky hierarchy per se was in a lovely little book I could not afford that I read in a Barnes and Noble in North Carolina in the 1990s. It was by Niklaus Wirth (whom you should know of) and, to my great delight, is available online. While dated, it’s still a great entry point into compilation and all that.

A hint or two about the dated aspects:

  • Parsing theory has enormously advanced. To be fair, the book wasn’t meant as a treatise on parsing at the time, but you should be careful about many useful assumptions he makes. For example, scannerless parsers (that is, ones without a separate lexical phase ) have received a fair bit of attention recently.
  • Compilation has hugely moved on. To pick just one thing, consider the commonality of JIT compilation (e.g., in the Java virtual machine).

That all being said, read it. The prose is lovely and there’s so much to be said for writing a small monograph.