Formal Language Theory: Refining the Chomsky Hierarchy Gerhard J¨ager & James Rogers 1 Introduction Thefieldofformallanguagetheory—initiatedbyNoamChomskyinthe1950s, building on earlier work by Axel Thue, Alan Turing, and Emil Post — provides a measuring stick for linguistic theories that sets a minimal limit of descriptive adequacy. Chomsky suggested a series of massive simplifications and abstrac- tionstotheempiricaldomainofnaturallanguage. (Inparticular, thisapproach ignoresmeaningentirely. Also,allissuesregardingtheusageofexpressions,like their frequency, context dependence, and processing complexity, are left out of consideration. Finally, it is assumed that patterns that are productive for short strings apply to strings of arbitrary length in an unrestricted way.) The im- mense success of this framework — influencing not just linguistics to this day, but also theoretical computer science and, more recently, molecular biology — suggests that these abstractions were well chosen, preserving essential aspects of the structure of natural languages.1 Anexpression inthesenseofformallanguagetheoryissimplyafinitestring ofsymbols,anda(formal)language isasetofsuchstrings. Thetheoryexplores themathematicalandcomputationalpropertiesofsuchsets. Asastartingpoint, formallanguagesareorganizedintoanestedhierarchyofincreasingcomplexity. Initsclassicalformulation[3],thisso-calledChomskyHierarchy hasfourlev- els of increasing complexity: regular, context-free, context-sensitive, and com- putably enumerable languages. Subsequent work in formal linguistics showed thatthisfour-folddistinctionistoocoarse-grainedtopindownthelevelofcom- plexity of natural languages along this domain. Therefore several refinements have been proposed. Of particular importance here are levels that extend the classofcontext-freelanguages—theso-calledmildlycontext-sensitivelanguages — and ones that further delimit the regular languages — the sub-regular hier- archy. In this article we will briefly recapitulate the characteristic properties of the four classical levels of the Chomsky Hierarchy and their (ir)relevance to the analysis for natural languages. We will do this in a semi-formal style that does not assume specific knowledge of discrete mathematics beyond elementary set theory. On this basis, we will explain the motivation and characteristics of the mildly context-sensitive and the sub-regular hierarchies. In this way we hope to give researchers working in Artificial Grammar Learning an iron ration of formallanguagetheorythathelpstorelateexperimentalworktoformalnotions of complexity. 1Authoratitivetextbooksonthisfieldare[11,30]. 1 2 The Chomsky Hierarchy A formal language in the sense of Formal Language Theory (FLT) is a set of sequences, or strings over some finite vocabulary Σ. When applied to natu- ral languages, the vocabulary is usually identified with words, morphemes or sounds.2 FLT is a collection of mathematical and algorithmic tools about how to define formal languages with finite means, and and how to process them computationally. It is important to bear in mind that FLT is not concerned with the meanings of strings, nor with quantitative/statistical aspects like the frequency or probability of strings. This in no way suggests that these aspects are not important for the analysis of sets of strings in the real world — this is just not what FLT traditionally is about (even though it is of course possible to extend FLT accordingly — see Section 7). To be more specific, FLT deals with formal languages (= sets of strings) that can be defined by finite means, even if the language itself is infinite. The standard way to give such a finite description is with a grammar. Four things must be specified to define a grammar: a finite vocabulary of symbols (referred to as terminals) that appear in the strings of the language; a second finite vocabulary of extra symbols called non-terminals; a special designated non- terminal called the start symbol; and a finite set of rules. From now on we will assume that when we refer to a grammar G we refer to a quadruple hΣ,NT,S,Ri, where Σ is the set of terminals, NT is the set of non-terminals, S is the start symbol, and R is the set of rules. Rules have the form α→β, understood as meaning “α may be replaced by β”, where α and β are strings of symbols from Σ and/or NT. Application of the rule “α →β” to a string means finding a substring in it that is identical with α and replacing that substring by β, keeping the rest the same. Thus applying “α→β” to xαy produces xβy. G will be said to generate a string w consisting of symbols from Σ if and onlyifitispossibletostartwithS andproducew throughsomefinitesequence of rule applications. The sequence of modified strings that proceeds from S to w is called a derivation of w. The set of all strings that G can generate is called the language of G, and is notated L(G). The question whether a given string w is generated by a given grammar G is called the membership problem. It is decidable if there is a Turing machine (or an equivalent device, i.e. a computer program running on a machine with unlimitedmemoryandtimeresources)thatanswersthisquestionwith“yes”or “no”infinitetime. AgrammarG iscalleddecidable ifthemembershipproblem is decidable for every string of terminals of that grammar. In a slight abuse of terminology, a language is called decidable if it has a decidable grammar. A class of grammars/languages is called decidable if and only if all its members are decidable. 2This points to another simplification that is needed when applying FLT to natural lan- guages: In each language with productive word formation rules, the set of possible words is unbounded. Likewise, the set of morphemes is in principle unbounded if loans from other languages,acronymformationandsimilarprocessesaretakenintoconsiderations. Itiscom- monly assumed here that the object of investigation is an idealized language that does not undergochange. Whenthevocabularyitemsareidentifiedwithwords,itistacitlytakenfor granted that the words of a language form a finite number of grammatical categories, and thatitisthussufficienttoconsideronlyafinitenumberofinstancesofeachclass. 2 2.1 Computably enumerable languages Theclassofalllanguagesthatcanbedefinedbysomeformalgrammariscalled computably enumerable. It can be shown that any kind of formal, algorithmic procedurethatcanbepreciselydefinedcanalsobeexpressedbysomegrammar —beittherulesofchess,thederivationsoflogic,orthememorymanipulations of a computer program. In fact, any language that can be defined by a Turing machine (or an equivalent device) is computably enumerable, and vice versa. All computably enumerable languages are semi-decidable. This means that thereisaTuringmachinethattakesastringw asinputandoutputstheanswer “yes”ifandonlyifw isgeneratedbyG. Ifw isnotgeneratedbyG,themachine either outputs a different answer or it runs forever. Examples of languages with this property are the set of computer programs that halt after a finite number of steps (simply compile the program into a Turingmachineandletitrun,andthenoutput“yes”iftheprogramterminates), or the set of provable statements of first order logic. (A Turing machine can systematically list all proofs of theorems one after the other; if the last line of the proof equals the string in question: output “yes”; otherwise move on to the next proof.) 2.2 Context-sensitive languages Context-sensitive grammars3 are those grammars where the left hand side of each rule (α) is never longer than the right hand side (β). Context-sensitive languages are then the languages that can be defined by some context-sensitive grammar. The definition of this class of grammars immediately ensures a deci- sion procedure for the membership problem. Starting from a string in question w, there are finitely many ways in which rules can be applied backward to it. None of the resulting strings is longer than w. Repeating this procedure either leadstoshorterstringsortoaloopthatneednotbefurtherconsidered. Inthis way, it can be decided in finite time whether w is derivable from S. Even though the question whether or not a given string w is generated by a given context-sensitive grammar G is in principle decidable, computing this answer may be so complex algorithmically that it is, for practical purposes, intractable.4 It should be noted that there are decidable languages that are not context- sensitive (even though they don’t have any practical relevance in connection with natural languages). Examples of context-sensitive languages (that are not context-free) are (we follow the common notation where xi denotes a consecutive string of symbols that contains exactly i repetitions of the string x): • the set of all prime numbers (where each number n is represented by a string of length n), • the set of all square numbers, 3The term “context-sensitive” has only historical significance. It has noting to do with context-dependency in a non-technical sense in any way. The same applies to the term “context-free”. 4Intheterminologyofcomputationalcomplexitytheory,theproblemisPSPACEhard. 3 • the copy language, i.e. the set of all strings over Σ that consist of two identical halfs, • anbmcndm, • anbncn, and • anbncnenfn 2.3 Context-free languages In a context-free grammar, all rules take the form A→β, whereAisasinglenon-terminalsymbolandβ isastringofsymbols.5 Context- free languages are those languages that can be defined by a context-free gram- mar. Here the non-terminals can be interpreted as names of syntactic categories, andthearrow“→”canbeinterpretedas“consistsof”. Thereforethederivation of a string x in such a grammar implicitly imposes a hierarchical structure of x into ever larger sub-phrases. For this reason, context-free grammars/languages are sometimes referred to as phrase structure grammars/languages, and it is assumed that such languages have an intrinsic hierarchical structure. As hierarchical structure is inherent in many sequential phenomena in biol- ogy and culture — from problem solving to musical structure —, context-free grammars are a very versatile analytical tool. Itisimportanttokeepinmindthoughthatacontext-freelanguage(i.e.aset of strings) does not automatically come equipped with an intrinsic hierarchical structure. There may be several grammars for the same language that impose entirely different phrase structures. This point can be illustrated with the language (ab)n(cd)n. A simple gram- mar for it has only two rules: • S →abScd, • S →abcd. The derivation for the string abababcdcdcd can succinctly be represented by the phrase structure tree given in Figure 1. In such a tree diagram, each local tree (i.e. each node together with the nodes below it that are connected to it by a direct line) represents one rule application, with the node on top being the left-hand side and the nodes on the bottom the right-hand side. The sequence that is derived can be read off the leaves (the nodes from which no line extends downward) of the tree. The same language can also be described by a somewhat more complex grammar, using the rules: • S →aTd, 5Incontext-freegrammars,therighthandsideofarulemaybetheemptystring,whilein context-sensitive grammars this is not licit. Therefore, strictly speaking, not every context- freegrammariscontext-sensitive. Thisisaminortechnicalpointthoughthatcanbeignored inthepresentcontext. 4 S a b S c d a b S c d a b c d Figure 1: Phrase structure tree S a T d b S c a T d b S c a T d b c Figure 2: Different phrase structure tree for the same string • T →bSc, • T →bc. Accordingtothisgrammar,thephrasestructuretreeforabababcdcdcdcomes out as given in Figure 2. So both grammars impose a hierarchical structure on the string in question, but these structures differ considerably. It is thus important to keep in mind thatphrasestructuresaretiedtoparticulargrammarsandneednotbeintrinsic to the language as such. Natural languages often provide clues about the hierarchical structure of their sentences beyond the plain linear structure. (Intonation, semantic co- herence, morphological agreement and relative syntactic independence are fre- quently used criteria for a sub-string to be considered a coherent hierarchical unit.) Therefore most linguists require a grammar not just to generate the cor- 5 context-free languages non-context-free languages mirror language copy language (i.e. the set of strings xy over a (i.e. the set of strings xx over a givenΣsuchthatyisthemirror given Σ such that x is an arbi- image of x) trary string of symbols from Σ) palindrome language (i.e.thesetofstringsxthatare identical to their mirror image) anbn anbncn anbmcmdn anbmcndm well-formed programs of Python (or any other high-level programming language) Dyck language (the set of well-nested parentheses) well-formed arithmetic expression Table 1: Context-free and non-context-free languages rectsetofstringstobeadequate. Rather,itmustalsoassignaplausiblephrase structure. Themembershipproblemforcontext-freelanguagesissolvableincubictime, i.e.themaximumtimethatisneededtodecidewhetheragivenstringxbelongs to L(G) for some context-free grammar G grows with the third power of the lengthofx. Thismeansthatthereareefficientalgorithmstosolvethisproblem. Examplesof(non-regular)context-freelanguagesaregivenintheleftcolumn ofTable1. Whereappropriate,aminimallydifferingexampleforanon-context- free language (that are all context-sensitive) are given in the right column for contrast. 2.4 Regular languages Regular languages are those languages that are defined by regular grammars. In such a grammar, all rules take one of the following two forms: A → a, A → aB. Here A and B stand for non-terminal symbols and a for a terminal symbol.6 6Equivalently, we may demand that the rules take the form “A → a” or “A → Ba”, with the non-terminal, if present, preceding the terminal. It is crucial though that within a givengrammar,allrulesstartwithaterminalontheright-handside,orallrulesendwitha terminal. 6 regular languages non-regular languages anbm anbn thesetofstringsxsuchthatthe thesetofstringsxsuchthatthe number of as in x is a multiple numberofasandthenumberof of 4 bs in x are equal the set of natural numbers that leave a remainder of 3 when di- vided by 5 Table 2: Regular and non-regular languages As regular grammars are also context-free, the non-terminals can be seen as category symbols and the arrow as “consists of”. According to another natural interpretation, non-terminals are names of the states of an automaton. The arrow “→” symbolises possible state transitions, and the terminal on the right handsideisasymbolthatisemittedasasideeffectofthistransition. Thestart symbol S designates the initial state, and rules without a non-terminal on the right hand side represent transitions into the final state. As there are finitely manynon-terminals,aregulargrammarthusdescribesafinite state automaton. In fact, it can be shown that each finite state automaton can be transformed into one that is described by a regular grammar without altering the language that is being described. Therefore regular grammars/languages are frequently referred to as finite state grammars/languages. Themembershipproblemforregularlanguagescanbesolvedinlineartime, i.e.therecognitiontimegrowsatmostproportionallytothelengthofthestring inquestion. Regularlanguagescanthusbeprocessedcomputationallyinavery efficient way. Table 2 gives some examples of regular languages in the left column. They are contrasted to similar non-regular (context-free) languages in the right col- umn. Astheexamplesillustrate,regulargrammarsareabletocountuptoacertain number. This number may be arbitrarily large, but for each regular grammar, there is an upper limit for counting. No regular grammars is able to count two sets of symbols and compare their size if this size is potentially unlimited. As a consequence, anbn is not regular. The full proof of this fact goes beyond the scope of this overview article, and the interested reader is referred to the literature cited. The crucial insight underlying this proof is quite intuitive though, and we will give a brief sketch. For each regular grammer G, it is possible to construct an algorithm (a finite state automaton) that reads a string from left to right, and then outputs “yes” if the string belongs to L(G), and “no” otherwise. At each point in time, this algorithm is in one of k + 1 different states, where k is the number of non-terminals in G. Suppose, for a reductio ad absurdum, that L = anbn is a regular language, and let G∗ be a regular grammar that recognizes L and that has k∗ non-terminals. Then the corresponding recognition algorithm has k∗+1 different states. Now let i be some number > k∗+1. According to the assumption, aibi belongs to L(G). When the recognition algorithm reads in the 7 Figure 3: Chomsky Hierarchy sequence of as at the beginning of the string, it will visit the same state for the second time after at most k∗+1 steps. So a sequence of i consecutive as will be indistinguishable for the algorithm from a sequence of i−k′ consecutive as, for some positive k′ ≤k∗+1. Hence, if the algorithm accepts the string aibi, it will also accept the string ai−k′bi. As this string does not belong to anbn, the algorithmdoesnotacceptallandonlytheelementsofanbn,contraassumption. Therefore anbn cannot be a regular language. As mentioned above, each regular language corresponds to some finite state automaton, i.e. an algorithm that consumes one symbol at a time and changes its state according to the symbol consumed. As the name suggests, such an automaton has finitely many states. Conversely, each finite state automaton can be transformed into a regular grammar G such that the automaton accepts all and only the strings in L(G). The other levels of the Chomsky Hierarchy likewise each correspond to a specific class of automata. Context-free grammars correspond to finite state automatathatareadditionallyequippedwithapushdown stack. Whenreading an input symbol, such a machine can — next to changing its state — add an item on top of a stack, or remove an item from the top of the stack. Context-sensitivegrammarscorrespondtolinearlyboundedautomata. These are essentially Turing machines, i.e. finite state automata with a memory tape thatcanperformarbitraryoperations(writinganderasingsymbolsonthetape and moving the tape in either direction) during state transitions. The length of the available tape is not infinite though but bounded by a number that is a linear function of the length of the input string. Finally, Type-0 grammars correspond to unrestricted Turing machines. 8 Neither did John claim that he neither smokes while ... nor snores, nor did anybody believe it. Figure 4: Nested dependencies in English dass mer d’chind em Hans es Huus lo¨nd h¨alfe aanstriiche that we the children-ACC Hans-DAT the house-ACC let help paint ‘that we let the children help Hans paint the house’ Figure 5: Cross-serial dependencies in Swiss German 3 Where are natural languages located? The issue where natural languages are located within this hierarchy has been an open problem over decades. Chomksky [4] pointed out already in the 1950s that English is not a regular language, and this argument probably carries over to all other natural languages. The crucial insight here is that English has cen- tre embedding constructions. These are constructions involving two dependent elements a and b that are not adjacent, and that may contain another instance of the same construction between the two parts. An example are neither-nor constructions, as illustrated in Figure 4. The pair-wise dependencies between neither and nor are nested. As far as the grammar of English goes, there is no fixed upper bound on the number of levels of embedding.7 Consequently, English grammar allows for a potentially unlimited number of nested depen- dencies of unlimited size. Regular grammars are unable to recognize this kind of unlimited dependencies because this involves counting and comparing. As mentioned at the end of the previous section, regular languages cannot do this. The issue whether all natural languages are context-free proved to be more tricky.8 Itwasfinallysettledonlyinthemid-1980s,independentlybytheschol- ars Riny Huybregt ([12]), Stuart Shieber ([29]), and Christopher Culy ([7]). HuybregtsandShieberuseessentiallythesameargument. Theynoticethatthe dependencies between verbs and their objects in Swiss German are unbounded in length. However, they are not nested, but rather interleaved so that they cross each other. An example (taken from [29]) is given in Figure 5. Here the first in a series of three article-noun phrases (d’chind ’the child’) is the object of the first verb, lo¨nd ’let’ (lo¨nd requires its object to be in ac- cusative case and d’chind is in accusative); the second article-noun phrase (em 7Notethathereoneoftheidealizationsmentionedabovecomeintoplayhere: Itistaken forgrantedthataproductivepattern—forminganeither-nor constructionoutoftwogram- matical sentences — can be applied to arbitrarily large sentences to form an even larger sentence. 8Here we strictly refer to the problem whether the set of strings of grammatical English sentencesisacontext-freelanguage,disregardingallfurthercriteriaforthelinguisticadequacy ofagrammaticaldescription. 9 Hans,’Hans’,carryingdativecase)istheobjectofthesecondverb(h¨alfe ’help’, which requires its object to be in dative case) and the third article-noun phrase (es Huus ’the house’, accusative case) is the object of the third verb (aanstri- iche ’paint’, which requires an accusative object). In English, as shown in the glosses, each verb is directly adjacent to its object, which could be captured even by a regular grammar. Swiss German, however, has crossing dependencies betweenobjectsandverbs, andthenumberoftheseinterlockeddependenciesis potentially unbounded. Context-free grammars can only handle an unbounded numberofinterlockeddependenciesif they are nested. ThereforeSwiss-German cannot be context-free. Culy makes a case that the rules of word formation in the West-African language Bambara conspire to create unbounded crossing dependenciesaswell,thusestablishingthenon-context-freenessofthislanguage of well-formed words. Simple toy languages displaying the same structural properties are the copy language —whereeachgrammatical stringhastheformww forsomearbitrary string w, and this creates dependencies the corresponding symbols in the first and the second half of the string — and anbmcndm, where the dependencies between the as and the cs include an unlimited number of open dependencies reaching from the bs to the ds. Therefore both languages are not context-free. 4 Mildly context-sensitive languages After this brief recapitulation of the “classical” Chomsky Hierarchy, the rest of the paper will review two extensions that have proven useful in linguistics and cognitive science. The first one — dealt with in this section — considers levels between context-free and context-sensitive languages; so-called mildly context- sensitive languages. Thefollowingsectionisdevotedtothesubregularhierarchy, acollectionoflanguageclassesthatarestrictlyincludedintheregularlanguages. Since the 1980s, several attempts have been made to design grammar for- malisms that are more suitable for doing linguistics than the rewrite grammars fromtheChomskyHierarchy,whileatthesametimeapproximatingthecompu- tational tractability of context-free grammars. The most prominent examples are Aravind Joshi’s Tree Adjoining Grammar (see [13]) and Mark Steedman’s Combinatory Categorial Grammar ([1, 33]). In 1991, [14] proved that four of theseformalisms(thetwoalreadymentionedones,plusGeraldGazdar’s[8]Lin- ear Indexed Grammars andCarlPollard’s[20]Head Grammars)areequivalent, i.e. they describe the same class of languages. A series of related attempts to further extend the empirical coverage of such formalisms and to gain a deeper understanding of their mathematical properties converged to another class of mutually equivalent formalisms (including David Weir’s [35] Linear Context- Free Rewrite Systems and Set-Local Multi-Component TAGs, and Ed Stabler’s [31] formalisation of Noam Chomsky’s [5] Minimalist Grammars) that describe anevenlargerclassofformallanguages. Astherearenocommontermsforthese classes, we will refer to the smaller one as TAG-languages (TAG abbreviating Tree Adjoining Grammar) and the larger one MG-languages (MG abbreviating Minimalist Grammar). ThemembershipproblemforTAGlanguagesisO(n6),i.e.thetimethatthe algorithmtakesgrowswiththe6thpowerofthelengthofthestringinquestion. Non-context free languages that belong to the TAG languages are for instance 10