2.1. What is phonology?

I assume that the reader of this article has some background in formal linguistics, perhaps equivalent to a one-year undergraduate sequence covering phonetics, phonology, and other core areas. For example, I assume the reader is familiar with the concept of underlying representation (UR; also called lexical representation, or input) versus surface (SR; also called output), and the convention that URs are indicated with slashes // while SRs are indicated with brackets []; I assume knowledge of the terms 'segment', 'syllable', 'onset', 'coda', et cetera, and the International Phonetic Alphabet. Still, as I anticipate some readers will come from a computational background where the study of speech sounds is not emphasized, I will briefly describe here core concepts which figure prominently in the paper.

2.2. Probability

I assume the reader is familiar with elementary statistics and probability theory. For example, I assume the reader is familiar with the concept of p-value, t-test, and use of the binomial formula to calculate the probability of a series of coin tosses. I also assume the reader is familiar with exponentiation and the inverse operation of taking the logarithm. Below I describe the concept of odds, and briefly outline log-linear models.

3.1. General overview

In formal language theory, 'language' does not refer to a shared linguistic code like English or Amharic or Tashliyt Berber. Rather, it is a formal object with precisely specified properties, which can be studied in a mathematical, axiomatic, logical fashion. Conventionally, formal language theory assumes an alphabet Σ and defines a string as an ordered sequence of elements from Σ. For example, if Σ = {a, b} then σ = ab is a (rather short) string over Σ. The set of all possible strings over Σ is denoted Σ^* (where ^* is called the Kleene star and has the conventionalized meaning of “0 or more repetitions”). Normally in formal language theory, a language L is defined as a subset of Σ^*. Note that the elements of the alphabet do not have any intrinsic meaning, or any internal structure; they are simply algebraic elements that are distinct from one another.

For example, we could define Σ = {C, V} and L = (CV)⁺ (where ⁺ means “1 or more repetitions”); the resulting set of strings would look to a phonologist like a strict CV language: {CV, CVCV, CVCVCV, ...}. But the formalism does not know that C means consonant and V means vowel in the same way that human speakers do. Humans know that vowels are characterized partially complementary articulatory and acoustic properties, as well as sequencing facts (e.g. words must begin with a C, every C must be followed by a V, V can end a word or be followed by a C). The formalism merely knows the sequencing facts, and that C is a different symbol than V. Indeed, the language L = (ab)⁺ over Σ = {a, b} has the same abstract structure as L = (CV)+ over Σ = {C, V}; from a formal language perspective, these are notational variants, meaning that they express the same pattern after a transparent, structure-preserving change in notation.

Interest in formal language theory is motivated by the assumption that natural languages can be mapped onto some particular class of formal languages (or vice versa), and that the properties of the formal language class will yield clear insights into how language is learned, represented and computed in the minds of speakers. For example, it is widely believed that syntax is mildly context-sensitive, while phonology is (sub)regular (e.g. Heinz, 2011a, b; Stabler, 2009). We will unpack this assertion later. In the meantime, it must be acknowledged this idea of identifying languages with stringsets, and dividing them up into classes based upon certain properties, is a large assumption, whose full implications we do not have space to assess here. I will point out one implication here however: the literature on learning formal languages ('learnability') assumes that knowledge that is 'outside' the grammar is not brought to bear on grammar learning. For example, phonetic knowledge does not figure in the formal language learnability literature on phonology, just as semantic/pragmatic knowledge does not figure in the learnability literature on syntax. With this kind of caveat in mind, let us consider what formal language theorists mean by a language class.

3.2. The Chomsky Hierarchy

It may be helpful to begin with an example. Chomsky (1956) describes a way of generating strings that is now known as a phrase-structure grammar. Phrase-structure grammars are predicated on a system of “rewrite rules”, in which one string is rewritten as another. Here is an example of an especially simple phrase-structure grammar:

The S symbol is underlined to indicate that it is the unique start symbol. This grammar generates strings by beginning with the start symbol, and generating all possible outputs by applying any rule that can apply, at any time. For example, this grammar generates the string the boy likes the boy by rewriting 'S → NP VP', 'NP → the boy', 'VP → V NP', and 'NP → the boy' again. The sequence of rewrite operations, together with the final output of the derivation, has an elegant visual representation as a tree:

The grammar in (5) is simple enough to enumerate the entire language it generates: the boy likes the boy, the boy likes the dog, the dog likes the boy, the dog likes the dog.

More formally, a phrase-structure grammar G consists of a start symbol S, a set of terminal symbols Σ, a set of nonterminal symbols V (which must not share any symbols with Σ), and a collection of rewrite rules R, where each rewrite rule maps a sequence containing a nonterminal to a sequence of terminals and nonterminals. The language generated by such a grammar is defined as the set of strings generated by all derivations that terminate (i.e. strings containing only terminal symbols).

3.3. Equivalency of Finite State Automata and Regular Languages

An overview of formal language theory would not be complete without mention of finite state machines (FSMs, also called FSAs for finite state automata). Practically speaking, an FSM is an alternative representation of a regular language. Historically, the two were conceived of separately, but the formal equivalence was noted and proved in early work. An FSM consists of a set of states, conventionally indicated with circles and an optional state label. In addition to the states, an FSM contains transitions between states, which must be labeled in most formulations. At least one state is designated as a start state, and at least one state is designated as an end state; these may be the same state. Conventionally, the start state is indicated with a thick circle, while other states are indicated with a single circle. Here are two examples:

Finite state machines can be considered as generators or parsers, but either way, they describe the same set of strings. Example (9) describes exactly two strings: Hello father, and Hello world. Example (10) describes an infinite number of strings, including This is the cat, This is the cat that chased the rat, This is the cat that chased the rat that ate the cheese, This is the cat that ate the cheese that chased the rat, etc. In generation mode, the FSM works by beginning at the start state. If it is at an end state, it may stop, having generated a complete string. If there are one or more transitions out of the current state, the machine selects one randomly and follows it, emitting a symbol along the way (the label on the transition). However, when there is only one transition out of a non-end-state, the machine must follow that unique transition. In parsing mode, the machine is said to consume symbols from an input string. It begins at the start state. When it receives the next symbol from the input string, it looks for a transition with a matching label. If there is a matching transition, it follows it and advances to the next input symbol. If there is not a matching label, the machine is said to reject the string. If the machine is in an end state when the input string is entirely consumed, the machine is said to accept the string; otherwise the machine rejects the string. In other words, the FSM accepts the string if and only if it can match every symbol in the input string with a transition and end up in an end state when the input is consumed.

An example of a string that (10) does not accept is This was the cat that chased the rat. Initially, the machine is in the start state (S₁). The first input symbol, This, is presented and matches the label for the transition leading out of S₁ and into S₂, so This is consumed and the machine enters state S₂. Now the input symbol was is considered, but the only available transition label is is, so the machine rejects the string. In formal language theory, accepting or rejecting a string is akin to offering a grammaticality judgment. Languages are defined as sets of strings, so in principle it is possible to make a binary judgment for every string, whether it is in the language. In the case of regular languages, there is guaranteed to be a finite state machine which can not only do this is principle, but can do so straightforwardly and efficiently in a computer implementation. For this reason, finite state methods have been applied throughout computer science, for both natural language processing and various other applications (such as programming language parsing and compilers).

It is worth noting here that there are alternative formulations of finite state machines. For example, it is possible to make the state labels correspond to symbols being generated/consumed, while the transitions are unlabelled. It is also possible to augment the transition and/or states with extra information, beyond the symbol being consumed/generated. Indeed, there is a great deal of work on this topic, which is omitted for space reasons.

A final type of finite state automata is known as a finite state transducer (FSTs). An FST is just like an FSM, except that it parses an input string and generates a corresponding output string. That is, the FST behaves just like a FSM in terms of parsing, but its transition labels have been augmented; the label consists of both the input symbol to match, and an output symbol to generate upon a successful match. Here is an example which implements an intervocalic lenition rule (d → ð / a__a):

The symbol ∈ is a special symbol, conventionally used to indicate an empty output. The finite state transducer in (11) will first match an /a/ and output an [a]; then it will match a /d/ but output nothing, waiting to see if it gets another /a/. If it gets another /a/, it will then output the 'delayed' [ð] along with the [a]; otherwise, the FST will reject the string, indicating that the lenition rule does not apply to this input.

3.4. Identification in the limit, and other notions of learnability

Gold (1967) provided the first formalization of learnability for a formal language. In Gold's conception, the input to a learner is defined as a textT –an infinite sequence (t₁, t₂, ...) of grammatical items from a language L, which is guaranteed to contain every item in L at least once, but not in any particular order. A grammar G(L) is defined as a finite representation that can generate all and only the strings of L. A learner A is defined as a function which accepts a finite subsequence T_n = (t₁, t₂, ..., t_n) from a text T and returns a hypothesized grammar. For example, A(T₅) is the grammar that learner A would posit after hearing the first 5 sentences of L in text T. By feeding a learner A successively longer subsequences from an input text T, we obtain a sequence of posited grammars A(T₁), A(T₂), ... A learner is said to identify L in the limit if for every text T, there is a finite amount of input N such that A(T_N) = G(L), and A(T_m) = A(T_N) for all m > N. In other words, the learner A is said to identify L in the limit if they are guaranteed to converge on a grammar that generates L in a finite amount of time.

Prior to presenting Gold's main result, it is worth considering how this framework compares with the child's learning situation. In the framework described above, a learner has access only to positive evidence, that is, only to sentences which are actually in the language. This is now referred to as unsupervised learning, since the learner does not have access to an external metric or 'objective function' which unambiguously indicates the nature of the solution to be learned. (Gold also considered supervised learning, in the form of an informant who presents both sentences from the language and sentences not from the language, while indicating which is which.) It is generally believed that children acquire the syntax of their language from positive evidence only, and tend to ignore the negative evidence they do get (R. Brown, 1973). On the other hand, Gold's framework does not allow for 'meaning', either the semantic meaning of the words that sentences hear, or the 'phonetic' meaning of the phonemes that make up those words. Moreover, Gold's notion of identification in the limit does not impose any constraints upon the input text, such as some kind of 'representativeness' criterion. That is, it is a safe bet that the words 'momma' or 'mother' appear in the first million words that every English-acquiring infant hears, but there is nothing in Gold's formulation which requires input texts to exhibit this kind of real-world distributional property. Thus, Gold's assumptions line up with the child's learning situation in one way, but differ from it in other ways.

There were two key results in Gold (1967). The first is that the class of regular languages is not identifiable in the limit. The second was that regular languages (and even higher classes in the Chomsky hierarchy) are learnable in the limit from an informant, i.e. supervised learning with positive and negative examples. Since phonology is believed to be (sub)regular, and syntax is believed to be at least context-free, and it is widely believed that children do eventually learn the correct grammar for their language, this result is interpreted by many theorists as proving that children possess innate constraints on the space of hypotheses that they consider as grammars for their language.

This conclusion does not actually follow from Gold's theorem. In general, one can only reason 'backwards' from a model to reality when one is confident that the model is an accurate portrayal of the reality it is modeling. That is, modeling results depend on a host of assumptions; they are akin to a logical proposition of the form, 'If A and B and C and D, then X'. We cannot conclude from the truth of X that A and B and C and D are true. Moreover, we cannot conclude from the falsity of X that a particular assumption (e.g. C) is false; we can only conclude that some assumption is false. So from Gold's theorem, what we can conclude is quite limited. It could be that children are born with innate constraints on the grammars that they consider. But it also could be that the input is far more constrained than Gold assumes. It could be that children leverage multiple types of information (such as semantics and phonetics) in language acquisition, and that this provides extra constraints on the space of possible grammars. It could be that human grammars are not strictly comparable with the classes of string-generators that Gold considers. It is possible that humans do not actually converge a single final grammar state, and actually do update their grammars on the basis of new input throughout the lifespan. These possibilities are all compatible with Gold's theorem.

Close inspection of the proof for Gold's theorem reveals that it depends crucially on the order in which examples are presented. Gold shows that it is possible to construct a text which continually forces the learner to update their hypothesis, because the class of regular languages is rich enough that one can 'maliciously' deny crucial evidence to the learner ad infinitum. Valiant (1984) introduced a probabilistic framework for studying (machine) learning known as probably approximately correct (PAC). Abstracting away from the technical details, the key difference is that texts are required to be 'representative', in the sense that training examples must be drawn from a probability distribution, and the learner is counted as 'approximately correct' if its generalization errors on this distribution fall below an arbitrary threshold δ (which can be made as small as desired, as long as it is still greater than 0). A language class is said to be PAC-learnable if a learner can identify an 'approximately correct' language in the hypothesis space from a finite sample of the target language. It is efficiently PAC-learnable if there is an algorithm which is guaranteed to do this while requiring a number of examples that is polynomial in the size of the language. Kearns and Valiant (1994) show that regular languages are not efficiently PAC-learnable, while Li and Vitányi (1991) show that regular languages are efficiently PAC-learnable under the additional assumption that 'simple' examples are more likely to be drawn than complex ones (as assessed by a measure called Kolmogorov complexity).

Researchers have interpreted these learnability results in many ways. Some researchers believe that the way forward is to develop increasingly fine-grained specification of the assumptions and increasingly fine-grained classifications of the classes of languages. Some researchers believe that this kind of work simply has no bearing on the learning problem that children actually face. One generalization that many parties can agree to is that the learnability results offered so far are fragile, in the sense that seemingly small changes in the assumptions can result in large changes in the nature of the conclusion (while intuitively similar changes may also yield no meaningful difference). Thus, one way to view the careful work done by Gold, Valiant and others is as an ongoing attempt to characterize which assumptions actually matter for learnability.

There is a vast amount of work on formal language theory and learnability that cannot be surveyed here; I trust the presentation above was detailed enough to give the lay reader a sense of what formal language theory aims to accomplish. In the remainder of this section, I turn to two new lines of work in formal language theory with the potential to inform basic questions in phonology. The first concerns what might be called framework comparison –a methodology for comparing two distinct linguistic formalisms via the formal languages they generate. The second concerns the use of finite-state techniques for efficient implementations of constraint-based phonology, which I will refer to as finite-state OT.

3.5. Framework comparison

Modern linguistics has taken seriously the task of formalizing theoretical intuitions. From seminal works to the modern day, theorists are apt to propose new frameworks like SPE (Chomsky & Halle, 1968) and OT (Prince & Smolensky, 1993, 2002, 2004), or non-trivial departures from existing frameworks, such as autosegmental phonology (Goldsmith, 1976, 1990; McCarthy, 1981), Harmonic Serialism (McCarthy, 2008, 2011), and others. The formalist bent has paid off in theoretical precision: so long as the linguistic atoms and operations are specified, the reader of a paper can make new predictions from a theory which the original writer would agree with. This kind of precision enables rapid progress, and surely reduces the frequency and severity of fruitless debates in the field over misinterpretations of a theory. Still, as pointed out in Stabler (2009), the proliferation of theories does come with a cost. In many cases there are competing formalisms, but since the surface character of the explanation is so different, it is difficult to tell whether the theories actually make different predictions.

Formal language theory offers a way to directly compare the expressive and restrictive powers of two different frameworks. This kind of work is already well-established in the syntactic domain, as evident from the following quotation in a review by Stabler (2009):

In the work of Joshi, Vijay-Shanker, and Weir (1991), Seki et al. (1991), and Vijay-Shanker and Weir (1994) four independently proposed grammar formalisms are shown to define exactly the same languages: a kind of head-based phrase structure grammars (HGs), combinatory categorial grammars (CCGs), tree adjoining grammar (TAGs), and linear indexed grammars (LIGs). Furthermore, this class of languages is included in an infinite hierarchy of languages that are defined by multiple context free grammars (MCFG), multiple component tree adjoining grammars (MCTAGs), linear context free rewrite systems (LCFRSs), and other systems. Later, it was shown a certain kind of “minimalist grammar” (MG), a formulation of the core mechanisms of Chomskian syntax –using the operations merge, move, and a certain strict 'shortest move condition'– define exactly the same class of languages (Michaelis, 2001; Harkema, 2001; Michaelis, 1998). These classes of languages are positioned between the languages defined by context free grammars (CFGs) and the languages defined by context sensitive grammars (CSGs) like this.

The works cited by Stabler indicate that despite the surface differences between formal frameworks, they are sometimes “notational variants”, in the deep sense that they describe the same set of languages. The details of these proofs are beyond the scope of this article, but the general nature of the argument is clear: provide a schema for translating one formalism into a particular kind of logic, which can be expressed as a formal language. Then do the same for the other formalism, and show that the two resulting formal languages are the same (or different) according to known properties of the formal language. In the view of the researchers who do this work, formal language theory has a certain potential to tell us what our formal mechanisms are actually buying for us.

Kaplan and Kay (1994) arguably supplied the first such example of this line of work in phonology. They proved that the rule-based rewrite system presented in SPE belongs to the class of regular languages, by embedding it in a class of logics known as Monadic Second Order (MSO) logics, known to be equivalent to the regular languages. More precisely, Kaplan and Kay claimed that SPE was regular even with 'cyclical rules' that are allowed to feed its own environment, as long as they are forbidden from feeding their own targets (for discussion and clarification see Kaplan & Kay, 1994). Potts & Pullum (2002) did essentially the same thing with OT, embedding a class of OT constraints into MSO. In addition, Potts & Pullum demonstrated that particular classes of OT constraints that had been proposed (e.g. align constraints) exceeded the power of regular languages, and in some cases they proposed regular alternatives.

Graf (2010a, b) compared a formalism known as Government Phonology with SPE. For readers not already familiar with Government Phonology, Graf (2010a) very readably points out the vast surface differences between it and SPE:

GP as defined in Kaye et al. (1985, 1990) and Kaye (2000) differs from SPE in that it uses privative features (features without values) rather than binary ones, assembles these features in operator-head pairs instead of feature matrices, builds its structures according to an elaborate syllable template, employs empty categories and allows all features to spread (just like tone features in autosegmental phonology). (p. 83)

Graf begins by translating each of these formalisms into a kind of propositional logic. Like Kaplan and Kay (1994), Graf embeds SPE in MSO. Graf goes on to show that if Government Phonology allows unbounded feature spreading, it can be embedded in MSO; if it allows only bounded spreading, it can be embedded in a strictly less expressive logic. In other words, Graf argues that despite the many differences between these formalisms, the property that really matters is bounded vs. unbounded spreading, since with unbounded spreading the two theories can express the same languages.

Graf goes on to address the 'empirical bite' of this theory by asking whether any natural phonological phenomena do require unbounded feature spreading. He proposes two candidates –Sanskrit nati and Cairene stress assignment. According to Graf, the nati rule causes an underlying /n/ (the TARGET) to become retroflexed if it is the first postvocalic /n/ after a continuant retroflex consonant (/ɻ/ or /ȿ/; the TRIGGER), provided that no coronal intervenes between the trigger and target, that the nasal target is immediately followed by a nonliquid sonorant, and that there is no retroflex continuant in the string after the target. As for Cairene stress assignment, the rule is to stress the final if it is superheavy or the penult if it is heavy. If both the final syllable and the penult are light, the rule is to stress the penult or the antepenult, whichever is an even number of syllables from the closest preceding heavy syllable. This suggests the presence of an 'invisible' trochaic footing system, in which secondary stresses propagate in an iterative/bounded manner from the rightmost heavy to the penult or the antepenult. Of course, as Graf points out, the ability to analyze bounded/iterative spreading of an 'invisible' feature is empirically impossible to distinguish from unbounded spreading of a visible feature. Therefore, he proposes to ban bounded/iterative spreading of invisible features for the purposes of theory comparison. This suggests that unbounded feature spreading is required –an important theoretical claim.

Two other recent studies in this line of research are Jardine (in press) and Buccola and Sonderegger (2013). Jardine (in press), following directly from Graf (2010a, b), asks whether autosegmental phonology belongs to the same class as SPE. Jardine does not give a complete answer to this question, owing to phenomena such as floating tones and dissociation rules. However, Jardine does show that MSO is expressive enough to cover the 'simple' phenomena that initially motivated autosegmental phonology, such as rightward feature-spreading. Buccola and Sonderegger address Canadian raising, an opaque phonological pattern in which allophonic variation is triggered by an underlying contrast that is erased at the surface:

Patterns like (12) are easily captured by a rules-based analysis in which the tapping rule applies after the Canadian raising rule. It is generally believed that such patterns cannot be accommodated by 'normal' OT, and a considerable body of work has been devoted to accommodating the theory to this type of pattern. What Buccola and Sonderegger show is that for any version of OT in which there is a single stratum (that is, one input representation and one selected output representation, with no intervening representational levels subject to competition), and in which faithfulness constraints assess the relationship only between an input segment and its output correspondence (i.e. without reference to its neighbors), the OT theory is strictly unable to account for the opacity pattern. They show this by translating OT constraints into finite-state transducers, in the manner proposed by Riggle (2004) and described in the next subsection. However, Buccola and Sonderegger also acknowledge that the highly related formalism of Harmonic Grammar (in which constraint competitions are resolved through linear combinations rather than strict domination) actually can accommodate cases like Canadian raising, without allowing for so-called positional faithfulness constraints. (Finally, there is an analysis in which the [ʌ͡ɪ]~[a͡ɪ] contrast is treated as phonemic, although many linguists disprefer this, since it requires stipulating that [ʌ͡ɪ] is only licensed before coronal obstruents and [ɾ], and crucially fails to link this fact to the nearly complementary distribution of [a͡ɪ].)

In summary, formal language theory has begun to deliver on the promise of framework comparison in phonology. If one is willing to accept the premise that a language is a set of strings, this kind of technically exacting work has the capacity to reveal surprising equivalences between formalisms, and to zoom in on key properties which distinguish expressivity. Still, it must be acknowledged that existing work seems to depend sensitively on details of the analysis which are not themselves rock-solid. For example, the claim that syntax is not context-free rests on phenomena like cross-serial dependencies, and more specifically on the claim that Swiss German allows an unbounded number of them. In practice, it is likely quite rare for natural usage to yield more than 1 crossing dependency. While Graf's (2010a) work does not strictly depend on whether unbounded feature spreading actually occurs in phonology, it does suggest that this is a critical distinction phonologists should attend to. However, as he acknowledges, the two putative cases he gives have been contentious in the literature. Buccola and Sonderegger (2013) discuss Canadian raising and more generally counterfeeding on environment (Baković, 2011) and seem to endorse a rules-based approach, but there are alternative analyses that do not require ad hoc modifications to existing theories.

In conclusion, formal language theory offers a rigorous, string-based and axiomatic approach to phonology as a formal system. Many researchers believe that this kind of logic- or model-based approach to phonology is the key to discovering what formal properties of our frameworks make for meaningful contrasts in empirical coverage and restrictiveness. Other researchers are uneasy with this approach, a feeling which Stabler (2009) aptly summarized thusly:

But many linguists feel that even the strong claim that human languages are universally in the classes boxed in (1) is actually rather weak. They think this because, in terms of the sorts of things linguists describe in human languages, these computational claims tell us little about what human languages are like. (p. 203)

Looking back over the works reviewed above, it is clear that the formal language approach has relatively little to say about markedness, alternations, opacity, or many other core concerns of mainstream theoretical phonology.

For example, one of the most appealing aspects of constraint-based grammars is that they formally encode a substantive bias against marked structures, by directly including markedness constraint in the theory. Indeed, the success of OT in predicting the typology of syllable structures arises from the combination of an ONSET constraint (which punishes words that begin with a vowel) with a formal property called harmonic bounding (if candidate B is equal or worse on every dimension than candidate A, B can never win). OT thereby predicts the existence of languages which require words to begin with a consonant, and of languages which allow words to begin with a vowel, while correctly predicting the absence of languages which require words to begin with a vowel. But there is nothing about “regularity” which forces this property. Rather, it is part of the substantive content of the theory. Formal language theory simply has nothing to say about it.

In any case, it is clear that the formal language theory approach to framework comparison has just begun to affect phonology. There will be more of this work in the near future, not less. The eventual theoretical impact of this line of work cannot be determined yet, and is likely to depend on the extent to which theorists engage with well-established natural language data.

3.6. Finite-state OT

Mainstream phonological theory has undergone a paradigm shift with the innovation of constraint-based theories such as Optimality Theory (McCarthy & Prince, 1994; Prince & Smolensky, 1993, 2002, 2004). It was Ellison (1994) who first proposed a finite-state implementation of OT. The essence of the proposal was to construct an individual FST for each constraint. For example, with particular representational assumptions, the constraint *CODA can be encoded with (13):

In (13), the input is coded as pairs of syllable slots and segmental material, with O indicating an onset position, N the nucleus, C a coda, ε the empty string (a syllable position that is not filled), and ¬∈ any nonempty string (a syllable position that is filled). Thus, for example, when the syllabified form [al.qal.am.u] is run through the FST in (13), it is represented as in (14a), and the output is as in (14b):

In other words, the input string is transduced to a string of constraint violations, whose sum indicates the number of constraint violations for the candidate as a negative integer. Moreover, by constructing a regular expression which generates all possible syllabifications of /alqalmu/ and performing an operation known as intersection (also called the product), one can obtain the constraint violations for every possible syllabification. The advantage of doing this with finite-state methods is that they are amenable to memory- and operation-efficient computer implementation; in fact, standard finite-state libraries have been developed for most major computer programming languages.

Subsequent work has elaborated on this conception in various ways, although the core idea of writing constraints as FSTs has remained. For example, Karttunen (1998) proposed to compose constraints according to their ranking in a particular language with lenient composition, which efficiently removes candidates from the computation as soon as they become suboptimal, while allowing candidates to violate high-ranked constraints when there is no better competitor. Frank and Satta (1998) study the generative power of OT, and conclude that it is regular only if individual constraints can assign at most an n-ary distinction in well-formedness for some finite n. For example, the ALIGN family of constraints, which might penalize an element according to its (potentially unbounded) distance from the edge of a word, is suspect by these criteria.

Finite-state OT is particularly exciting to me because of its potential for the study of learning. The key ideas can be traced to a variety of papers. Goldwater and Johnson (2003) first noticed that Harmonic Grammars could be extended to log-linear (maximum entropy) models, simply by treating constraints as the feature functions. Berger et al. (1996) proved that under mild assumptions the likelihood function of log-linear models is convex in the weight space, which means that there is a unique maximum and it can be found efficiently using the gradient (the vector of derivatives with respect to each weight). Berger et al. further observed that the gradient can be calculated as O–E, where O_i is the observed violation count for constraint f_i in the training data, and E_i is the expected violation count. Eisner (2002, et seq.) and Riggle (2004, 2009) extended the finite-state conception of constraints with a special product operation that tracks the violation vector for an entire grammar, along with the vector's (log-)probability, using an algebraic structure referred to as a 'violation semiring'. The violation semiring construction offers computationally efficient computation of the weighted violation vectors for any regular class of strings. Therefore, it can be used to calculate the expected violation count E when that value is well-defined. Together, these results imply that a machine-implemented log-linear grammatical model can feasibly be trained. Hayes and Wilson (2008) actually implemented such a model in Java, and have been producing interesting work with it in subsequent papers. I will return to this model in the Cognitive Modeling section.

Heinz and colleagues have applied finite-state techniques to the acquisition of phonology. For example, Heinz (2007) treats the acquisition of long-distance phonological patterns (such as sibilant harmony, vowel harmony, and stress assignment) using finite-state learning. Heinz observes that all such long-distance phenomena exhibit a property he calls neighborhood distinctness, a property which enforces certain kinds of generalization, and which falls out naturally from applying a 'state merging' operation during construction of the FSM. Later work by Heinz considers learning various classes of subregular languages, often directly motivated by particular phenomena such as vowel harmony, and sometimes with proofs of identifiablility in the limit (Heinz, 2010; Heinz & Koirala, 2010; Heinz & Lai, 2013).

Formal language theory has developed a large body of axiomatic results on classes of 'languages', defined as stringsets generated intentionally by some finite, compact generative mechanisms. Work on this topic is generally concerned with 'learnability', which is typically formulated at an abstract, algebraic level. For example, a class of languages is identifiable in limit if an optimal learning algorithm can be guaranteed to converge upon the correct language in the class given an arbitrary sample of some size. Recent work on this topic has illustrated surprising insights on the expressive equivalence of formal frameworks with very different surface characteristics, and has provided powerful tools for implementing constraint-based phonology in computationally efficient finite state machines.

4.1. Zipfian distributions

It seems trivial, almost to the point of banality, to observe that some things happen more than others; for example, some words are repeated more frequently than others. However, the nature of the distribution can have powerful consequences for language acquisition and processing. It turns out that the variation in word frequencies is not completely random; it follows what has come to be known as a Zipfian distribution (Zipf, 1935, 1949). This means that a small number of items have a large frequency, and a large number of items have a small frequency. It is also sometimes informally described as 'most events are rare'.

Zipfian distributions are found at every level of linguistic structure. Baayen (2001) considers the implications of this fact for morphology. An essential point is that for any natural language text, the probability of encountering a new item never drops to zero. Therefore, a functioning model of language use must always allow for unseen items. The reader might be surprised to learn how much research does not provide for this. For example, the best-known and most-successful model of word recognition, TRACE (Elman & McClelland, 1985), does not have any explicit mechanism for handling so-called Out-of-Vocabulary (OoV) items. Daland and Pierrehumbert (2011) found that even segmental diphones (a consonant or vowel, followed by another consonant or vowel) exhibit a Zipfian distribution in English. Daland and Pierrehumbert go on to show that an English listener gets enough input in one day to approximate the frequency distribution over (frequent) diphones, yet might still encounter new pairs of speech sounds throughout their life. The enormous range of variation in frequencies has important but sometimes underappreciated implications for how learners might acquire phonology.

4.2. Statistical models

As noted above, the goal of many NLP and ASR researchers is to build language technologies that work, rather than focusing on the cognitive principles that underlie language use. Of course, those two goals are not mutually exclusive, but they are not identical either. In fact, the general experience of the NLP and ASR community has been that 'dumb' models with lots of training data perform better than 'smart' models with less training data:

I don't know how many of you work in IT have had this experience, but it's really awfully depressing to spend a year working on an interesting research idea and then discover you can get a bigger BLEU score increase by, say, doubling the size of your language model training data. I see a couple of nodding heads. --Phillip Resnick (in P. Brown & Mercer, 2013)

An example of a 'dumb' model in syntax is the Markov/n-gram models that Chomsky (1956) attacked as insufficient to explain various long-distance phenomena. From the perspective of NLP/ASR researchers, linguistic theory is good to the extent that it is useful and necessary for building systems that work:

It's not that we were against the use of linguistics theory, linguistic rules, or linguistic intuition. We just didn't know any linguistics. We knew how to build statistical models from very large quantities of data, and that was pretty much the only arrow in our quiver. We took an engineering approach and were perfectly happy to do whatever it took to make progress. In fact, soon after we began to translate some sentences with our crude word-based model, we realized the need to introduce some linguistics into those models... We replaced the words with morphs, and included some naïve syntactic transformation to handle things like questions, modifier position, complex verb tenses and the like... Now this is not the type of syntactic or morphological analysis that sets the linguist's heart aflutter, but it dramatically reduces vocabulary sizes and in turn improves the quality of the EM parameter estimates... From our point of view, it was not linguistics versus statistics; we saw linguistics and statistics fitting together synergistically. --Peter Brown (in P. Brown & Mercer, 2013)

A crucial contribution of NLP/ASR has been the insight that probabilistic approach to language modeling is necessary for developing real-world applications. Arguably, it is also inspiring a revolution in how we conceptualize language acquisition, or at least phonological acquisition.

This community has also developed machine-learning techniques that enable efficient estimation of model parameters. For example, commercial ASR technologies like Nuance Dragon rely on an acoustic model which relies on a 'dumb' Hidden Markov Model (HMM). An HMM is a close relative of a probabilistic FSM, with two key differences. First, the states themselves are latent variables (in the sense that the model builder posits that they exist, and they condition the model's output, but their parameters/relationships to other model components are learned during training). Second, emission of a string is not directly associated state transitions; rather, each state is associated with a probability distribution over observations. The acoustic observations are a time series {o^t}^t=1..M where each o^t is some kind of vector, typically generated by some kind of spectral decomposition of overlapping time frames from the waveform. For example, a simple HMM is shown in (15):

In this case, the task is to parse an acoustic sequence by labeling each discrete time frame as belonging to one of the categories 'C', 'V', or '<sil>' (silence). The acoustic observations have four dimensions, representing the absolute magnitude of the signal in the band 2000-5000 Hz, the entropy per Hertz in this band (a measure of aperiodicity), the absolute magnitude of the signal in the band 5000-10000 Hz, and the entropy per Hertz in this band. (Note that this type of acoustic representation is quite different from what is used in commercial applications. A concrete example is given to help the reader conceptualize an HMM. The parameters in (15) were not generated from actual speech data; they are included only for concreteness.) The solid lines represent state transitions, and the numbers represent the associated probabilities. Self-transitions take up the bulk of the probability in each case since normally the same vowel/consonant is spread over many observation frames. The 'emission probability' boxes characterize the likelihood of emitting the current observation o^t given the posited state s^t using a multi-dimensional normal distribution. For example, the 'C' label is associated with relatively lower amplitude and less periodicity than vowels in the 2-5 kHz band, and relatively higher amplitude but still less periodicity than vowels in the 5-10 kHz band.

Much of the early, seminal work in these fields focused on developing dynamic programming techniques to train these models efficiently from limited or very large amounts of training data. Especially well-known are the Viterbi algorithm for finding the most likely sequence of states given an observation sequence (Viterbi, 1967), and the Baum-Welch (or forward-backward) algorithm for finding the unknown parameters of an HMM (Baum & Petrie, 1966; Jelinek, Bahl, & Mercer, 1975). These algorithms, or modest adaptations/generalizations of them, are still used in most or many NLP papers published today, as well as in the finite-state OT methods described earlier and elaborated in more detail in later sections.

The discussion of NLP/ASR is necessarily brief. As emphasized throughout this discussion, NLP has made significant contributions to what now might be called computational phonology, although in practice NLP is interested in engineering applications (such as ASR) and is normally considered a separate field. The use of statistical models has transformed cognitive modeling in phonology, to which I turn next.

5.1. Phonotactic and phonological learning

The bulk of cognitive computational modeling of phonology that this author is aware of is concentrated in the areas of phonotactic and phonological learning. There are two key messages that this literature suggests to me. The first is that a constraint-based approach to phonological learning makes sense from a range of standpoints. The second is that a stochastic approach to phonological variation makes sense from a range of standpoints.

5.2. Word segmentation

Word segmentation is the perceptual process whereby listeners parse the speech stream into word-sized units. As evident from listening to speech in an unfamiliar language, many words are not followed by a silence or other language-general auditory boundary cue. However, fluent and normally-hearing listeners epiphenomenally report the sensation of hearing discrete words during speech perception, except under the most challenging listening conditions. Word segmentation refers to the cognitive process or processes that have applied between the auditory level and the listener's percept, of discrete words in a sequence.

One of the earliest computational approaches to word segmentation was the seminal TRACE model of speech perception, published by the already-mentioned PDP research group (Elman & McClelland, 1985). In this model, the listener is equipped with a bank of phonological features, a phoneme (or allophone) inventory, and an inventory of words. The 'auditory input' is represented as a time-varying vector of feature values. The model is a specific instance of a general class of models, quite popular in the psycholinguistic literature, known as 'spreading activation': the perceptual information from the 'bottom' (in this case, auditory featural) level percolates up to 'higher' levels (phonemes, and then words), and in some cases 'top-down' information also percolates downward. As a result, the 'output' of the model is a time-varying vector of word activations. The model is deemed to have successfully parsed a sentence if at the end of the sentence, all of the sentence's words are highly activated, and no other words are highly activated.

As Strauss, Harris, and Magnuson (2007) write:

Although TRACE was introduced 20 years ago, it continues to be vital in current work in speech perception and SWR. Despite well-known limitations (acknowledged in the original 1986 article and discussed below), TRACE is still the best available model, with the broadest and deepest coverage of the literature... TRACE has proved extremely flexible and continues to spur new research and provide a means for theory testing. For example, it has provided remarkably good fits to eyetracking data from recent studies of the time course of lexical activation and competition (Allopenna, Magnuson, & Tanenhaus, 1998; Dahan, Magnuson & Tanenhaus, 2001), including subtle effects of subphonemic stimulus manipulations (Dahan, Magnuson, Tanenhaus, & Hogan, 2001). (p. 20)

TRACE is mentioned here because, among other things, it has been claimed to account for word segmentation. The idea is that if you recognize the words themselves, the epiphenomenal percept of word segmentation has been explained. However, as hinted above, TRACE is not necessarily a viable model of acquisition. In particular, the model can only recognize words in its lexicon; no model-internal means is available for processing novel words and adding them to the lexicon. As is generally acknowledged in the literature on the acquisition of word segmentation, this is an essential aspect of the larger problem, since experimental evidence suggests that infants are able to segment previously unknown words, and indeed, this is the majority of new words that are learned (for argumentation see Daland & Pierrehumbert, 2011, and Goldwater, Griffiths, & Johnson, 2009).

Subsequent computational research on this topic employed corpus studies in combination with connectionist modeling (Aslin, Woodward, LaMendola, & Bever, 1996; Cairns, Shillcock, Chater, & Levy, 1997; Christiansen, Allen, & Seidenberg, 1998; Elman, 1990), with the promising result that relatively simple neural network models could predict word boundaries without necessarily recognizing the neighboring words. However, owing to the well-known difficulties with interpreting the internal representations of connectionist networks, this line of research stalled shortly after the initial wave, essentially because it proved impossible to reason from the modeling results to how infants actually solved the problem. Although this is a more general issue with modeling research, it proved especially acute here because it was not even possible to determine how the models solved the problem.

Nonetheless, the finding that prelexical segmentation was computationally practical had important consequences. Experimental evidence began pouring in around this time for phonotactic segmentation, meaning segmentation based on (knowledge of) likely, unlikely but permissible, and impermissible sequences within and across prosodic units such as words (e.g. Jusczyk, Hohne, & Baumann, 1999; Jusczyk, Houston, & Newsome, 1999; Mattys & Jusczyk, 2001; Saffran, Aslin, & Newport, 1996; for a more comprehensive review see Daland & Pierrehumbert, 2011). The experimental evidence shows quite clearly that infants can and do extract new wordforms from the speech stream, even from 'difficult' positions such as phrase-medially when there are good phonotactic cues.

This prompted a wave of computational models which attempted to solve the segmentation problem using only phonotactic knowledge. Early instances include Xanthos (2004) and Fleck (2008), who used utterance boundary information to infer lexical phonotactic properties, as originally suggested by Aslin, Woodward, LaMendola, and Bever (1996). A probabilistically rigorous bootstrapping model was formulated and tested in Daland and Pierrehumbert (2011) using diphones, sequences of two segments; in English, individual diphones typically have positional distributions that are highly skewed toward being either word-internal, or word-spanning, so that this phonotactic cue is an excellent one for word segmentation. Daland and Pierrehumbert advocate for a phonotactic approach to word segmentation because phonotactic segmentation becomes efficacious as soon as infants possess the necessary phonetic experience, around 9 months, consistent with the developmental evidence. Moreover, Daland and Pierrehumbert show that the phonotactic approach is robust to conversational reduction processes that occur in English. For example, it is well-known that word-final coronal stops are often deleted in conversational English; Daland and Pierrehumbert show that this kind of process causes only a modest decrement to their phonotactic model, but has rather more drastic effects on lexical models which use wordform recognition to do word segmentation (since current-generation lexical models assume the surface pronunciation of a wordform is its canonical and only form, their distributional assumptions are violated by speech containing pronunciation variation). Adriaans and Kager (2010) propose an analogous model in the framework of OT, which induces segmentation constraints from featural co-occurrence information.

The phonotactic approach has not panned out as well as its proponents originally hoped, however. As the empirical coverage widened to other languages, it became clear that phonotactic approaches always worked best for English (vs. Korean: Daland & Zuraw, 2013; vs. Spanish and Arabic: Fleck, 2008; vs. Japanese: Fourtassi, Börschinger, Johnson, & Dupoux, 2013; et alia). Moreover, the assumption (based on maternal questionnaires; Dale & Fenson, 1996) that 9-month-old infants barely knew any words was contradicted by experimental evidence (e.g. Mandel, Jusczyk, & Pisoni, 1995) suggesting that infants knew some wordforms as early as 4-6 months, even if they were not necessarily aware of the corresponding meanings.

In the meantime, the phonotactic approach to modeling word segmentation was overshadowed by the Bayesian, lexical approach developed by Goldwater, Johnson, and colleagues. This approach, which had its roots in the computational models of Batchelder (2002) and Brent and Cartwright (1996), returns to the view of word segmentation as an epiphenomenon of word recognition popularized in TRACE, but departs from TRACE in various ways. Most crucially, the models included means to add previously unencountered wordforms to its lexicon ('learn new words'); also, Brent and Cartwright (1996) defined an explicit and probabilistic mathematical objective which their model was supposed to maximize. Thus, Brent and Cartwright advocated for framing the segmentation problem at Marr's computational level ('What is the mathematical characterization of the function that humans optimize?') rather than the algorithmic level ('How do humans find the optimal solution for the function that they are optimizing?'). Goldwater, Griffiths, and Johnson (2009) extend the early work of Brent and Cartwright to a more general setting, factoring the learning problem so as to enable efficient optimization, reframing the objective in a Bayesian setting (rather than the related, but more restricted Minimal Description Length approach used by Brent and Cartwright; for discussion and analysis see Goldwater, 2006), and extending the data model so as to be both more powerful and more flexible. For example, Goldwater et al. (2009) show that better segmentation is predicted if infants attend to dependencies between words, a prediction that was retroactively confirmed by an experimental study showing that 6-month-olds use their own names to segment the following word (Bortfeld, Morgan, Golinkoff, & Rathbun, 2005).

Numerous authors have followed up on Goldwater and colleagues' seminal work. For example, Blanchard, Heinz, and Golinkoff (2010) adapt the model in Goldwater et al. (2009) by including an incremental n-gram phonotactic model, whose parameters are discovered during the learning process. They found a significant but very modest gain in performance, suggesting that much of the problem-solving power of Goldwater's model is actually located in the prior distribution (owing to reasons of space, I am unable to describe this model in more detail here; the reader is encouraged to consult the original paper for clear exposition). Pearl & colleagues have experimented with the idea that 'adding performance back in' to computational-level models can yield more psycholinguistically valid (and sometimes more accurate) performance, by incorporating limited short-term memory and/or long-term forgetting into Goldwater-like models (Pearl, Goldwater, & Steyvers, 2011; Phillips & Pearl, 2012). Lignos (2012) presents an incremental model with a slightly different objective than in Goldwater et al. (2009); an innovation is the use of a lexical filter which prevents low-confidence words from being incorporated into the model's lexicon. A variety of lexical filters have been used in previous work, including especially the constraint that a word must contain a vowel (Brent & Cartwright, 1996) or that it must have a certain minimal frequency (Daland & Pierrehumbert, 2011; see Ch. 5 of Daland, 2009, for modeling, analysis, and discussion of 'error snowballs' and Pearl et al., 2011, for argumentation that memory limitations help prevent error snowballs by forgetting early misparses).

The rapid, intense progress that has taken place in our understanding of word segmentation acquisition has been driven by an interplay and dialogue between a variety of research traditions, most notably developmental psycholinguists (Jusczyk, Mattys, Morgan, Saffran, etc.) and cognitive computational modelers (Daland, Goldwater, Johnson, Pearl, etc.), as well as researchers who are able to mix these methodologies (Aslin, Kager, Swingley, etc.). This is, in the author's humble opinion, a wonderful thing, and it is to be hoped that this example spreads to other domains.

More generally, the impact of cognitive modeling cannot be understated in linguistic theory and in cognitive science more generally. The interaction between domain-general and domain-specific representations and learning algorithms is a topic of perennial interest, and computational modeling has and continues to shed new light on the complexities. Modeling has in some cases clearly ruled out hypotheses as to cognitive processes that seemed a priori quite plausible; while in other cases it has shown that two formalisms which might naively be supposed to make completely divergent predictions actually offer statistically indistinguishable explanations for the very same data set (e.g. Jarosz, 2013). Just as with formal language theory for framework comparison, it is safe to predict that there will be more of this work in the future, not less. In the next and final content section of this review I turn briefly to the topic of corpus studies.