Chomsky Hierarchies, where math meets linguistics and computer language

 

Linocut 'Chomsky Hierarchy' by Ele Willoughby, 2021

This is one of the #mathyear prompts I had previously skipped. Chomsky hierarchies are the place math meets computer language and linguistics, and is something I have never studied, so I didn't have a good idea how to protray them. This year, I'm trying to do all the prompts I previously skipped, and I had a visiual idea.

This is a linocut portrait of linguist Noam Chomsky with a Venn diagram illustrating  the Chomsky hierarchy (or Chomsky-Schützenberger hierarchy) for formal grammars in formal language theory. In 1956, Noam Chomsky described the hierarchy of formal grammars (how to form strings from a language's alphabet that are valid according to the language's syntax). These ideas and hierarchy are pertinent for applied mathematics, theoretical computer science, theoretical linguistics and other areas.

He categoried 4 types of grammars, shown in the Venn diagram behind his portrait. Type 0, in pale yellow, contains recursively enumerable grammars, such that there exists a Turing machine which will enumerate all valid strings of the language. Type 1, in umber, contains context-sensitive grammars, are recognized by non-deterministic linear-bounded automata. Type 2, in orange, are context-free grammars, recognized by non-deterministic pushdown automaton. Type 3, in pink, are regular grammars, recognized by finite state automata.