What is the “Chomsky hierarchy”?

Question

What truly is the Chomsky hierarchy?

I know it aims to categorize core features of “languages”.

But what essential properties does each type have? Why are they so distinctive? Why are there four? And why is there nothing beyond “type-0”?

https://ncatlab.org/nlab/show/Chomsky+hierarchy

Answer 1

In the 50's, Chomsky set out to devise a mathematical theory of language, which resulted in classifying kinds of production rules. For example, if all rules in a grammar are of the form A → a A, or A → B a, where only capital letters (non-terminals) can be rewritten and a, b are single terminal symbols, we have one "type" of language (a "regular" language). A rule of the form A → α where α is any set of terminals and non-terminals puts the grammar in a different class, according to this analysis – it is a "context free" language. This classification of rules (grammars) is hierarchy in the sense that any rule that satisfies the definition of "regular" also satisfies the definition of "context free", but not the converse. The numbers then express that hierarchy, with type 3 being the least-powerful kind of rule, and type 0 being the most powerful. It also turns out that this system of "production rules" is equivalent to a hierarchy of machines from computer science, so a type 0 grammar is "equivalent" to a Turing machine. Mathematically speaking, there doesn't seem to be anything that a Turing machine can't do, if the thing can be done at all, at least if we are talking about computer algorithms. This is the original published article that introduces this way of looking at linguistic rules, though it was no doubt implicit in his dissertation etc.

What is distinctive, or what defines the kind of grammar we are talking about is the syntax of the production rules. There are additional rule types that we don't talk about. Rules of the form A → a A are right-linear rules, and A → A a defines left-linear rules, called "type 3.1 rules" – a subset of the type 3 rules. But the underlying interest was in discovering the classes of strings that can be generated by a particular rule type, and we don't care whether the rules are right-linear or left-linear, in that you can do the same things with right-linear vs. left-linear rules.

The ultimate goal of this line of investigation was to see what is the most powerful device required to generate human languages, so of course you need a method of quantifying "power" or "generative capacity".

Answer 2

I’m still learning, but I can give it a stab.

These ideas probably originate from Chomsky’s work in the late 1950’s to mid 1960’s.

I do not know how it precipitated, but it appears Chomsky’s teacher was Zellig Harris, who was also studying language mathematically. In fact, it appears that it was truly Zellig Harris who initiated a deeply mathematical study of language, as an extension of the work of some structural linguists and analytic philosophers.

There appears to be a profound chain of events in the history of ideas beginning from say, George Cantor and his invention of set theory to analyze some algebraic theories in 1800’s mathematics, which I suppose somehow led to Frege, who may have been the first “analytic philosopher” who explored the basis of truth and propositions as a logical system (?), and was taken further by Bertrand Russell and Alfred North Whitehead as they attempted to found all of mathematics in a particular system of type theory, similar to set theory.

Kurt Gödel demonstrated a famous theorem that I still cannot claim to genuinely have a personal understanding of, that axiomatic systems like set theory had intrinsic limitations; and this was partially a foundation for Alan Turing’s theories of how formal / axiomatizable systems have particular limits as well.

I do not know how directly this context washed up upon Chomsky’s shores. It is possible as an intellectually voracious person he simply exposed himself to general knowledge and saw the relevance to what he was thinking about and working on. It appears Turing’s core work happened in the mid to late 1930’s, so it would be interesting to consider if there were interesting developments from then until the 50’s that might have led Turing’s ideas to find application in linguistics. (Also, Turing attended a lecture by Wittgenstein.)

Claude Shannon also worked in early computer science and founded the modern discipline of information theory. Chomsky explicitly cites Claude Shannon in his early work, as for the first time he fully explored the idea of language not only as a mathematical system, as his teacher Harris, but as a computational system, a system of finite components whose arrangement is able to encode and transport “information”.

Chomsky looked at the abstract informational character of languages in general, regarding their grammar.

His abstract analysis of how certain types of rules determine certain features of languages built on those rules, as their grammar, is able to bridge linguistics to formal languages theory, and formal systems in general, such as set theory.

Chomsky’s classification of language into 4 classes is the following:

Finite state automata, or class 3.

These grammars can only transform one incoming input symbol at a time. I think a simple idea would be a game. I tell you the rules are, “If I say a word, you say a word that starts with the last letter of the word I say, like banana -> apple. The game ends when someone says “chicken”.”

This type of substitution process is like a Markov process, in that it only operates on one piece of input at a time.

Type 2, allows input to be strings, or multiple sequences of input elements. You can essentially wait to check what the whole incoming message is, before deciding what it is, and what to do about it. In a way, it means that a machine deciding what to do based on input has memory - it stores, or tracks, what it just got, and keeps track of what comes next, to see what the total message is.

Imagine a game where you have to keep track of a sequence - for example, a party game where everyone has to say a word in a category, that hasn’t been said yet. Your memory acts as a “stack”, in computer terms - a place where you record past input, and check if a word someone says was already said before (according to your memory). In computer terms, they are called “push down automata”, presumably because they have a mechanism that responds to input by “pushing” it onto some recording location - like an assembly line conveyor belt where incoming items accumulate in one place, until they are cleared away upon some decision.

Type 1 grammars allow for more complex substitutions than strings of input for finite output (terminal) symbols. Actually, they allow input symbols to be replaced by strings, which would be further parsed by the machine. In a way, this is like a “loop” in a program, where a command like “loop” causes the computer to replace that “symbol” with a command it must parse again. This is basically a “Turing machine”, with a subtle restriction of a kind of finitude, that the parsing or “game” will not go on forever. So, there are “repetition” rules, but you must carefully devise them to guarantee that there could not be an infinite loop (I think). In other words, you can repeat N times, but not command “loop forever, or loop until some condition which never comes.

Type 0 is considered a universal Turing machine: it has loops that never end.

The theory is well-described here, and hopefully soon, I can find the time to go through it. The important question is, why Chomsky felt this had such a bearing on the study of human languages. It is known there has been some disagreement about if human language may be type 1, context sensitive, or type 0, Turing-complete.

Hopefully someone can help me fill in the details there.

I believe a more broad view of why formal languages at least appear to have this natural/inherent classification may be viewable from category theory, so I will update this answer in an hour about my understanding on it.

https://ncatlab.org/nlab/show/formal+grammar

A bit more abstract view on such grammars from category theory is the following:

---

1. Define v as the vocabulary of a language - a set of elements.
2. v* is set of all possible combinations, or compositions, of those elements. But not all compositions may be considered valid or grammatical. So the language is a subset of that set of all possible combinations.
3. An unrestricted grammar is any set of rewrite rules imaginable on two sets: X, non-terminal elements, and V, the vocabulary, or terminal symbols.

Chomsky’s hierarchy can be seen as a series of restrictions on that most unrestricted form. For example, the excellent linked page below says:

Context free grammars are defined in the same way as unrestricted grammars, but they only allow rules with a single non-terminal symbol as domain. In that particular case, the grammatical derivations are trees with the start symbol as root and the words as leaves.

https://onlinelibrary.wiley.com/doi/abs/10.1002/9781119598732.ch5