ABSTRACT
A current Google search for “Chomsky Hierarchy” yields some 60,000 entries. They go beyond linguistics into computer science, algebra, statistics, communication theory, molecular biology, and even biophysics. Wikipedia reminds us that, within “the area of formal languages, the Chomsky Hierarchy (occasionally referred to as Chomsky-Schützenberger hierarchy) is a containment hierarchy a of classes of formal grammars … described by Noam Chomsky in 1956.” It then cites Chomsky’s famous 1956 Three Models for the Description of Language, and acknowledges Marco Schützenberger for having played a pivotal role in the development of the theory of formal languages. So as not to personalize matters, let’s refer to this notion as the Formal Language Hierarchy (FLH). 1
