2.2.7 Relating Deterministic and Non-Deterministic Automata

It may seem that allowing NFSAs to have non-deterministic features like $ \varepsilon $-transitions would make them more powerful than DFSAs. In fact this is not the case; for any NFSA, there is an exactly equivalent DFSA. In fact there is a simple algorithm for

converting an NFSA to an equivalent DFSA, although the number of states in this equivalent deterministic automaton may be much larger. See Lewis and Papadimitriou (1988) or Hopcroft and Ullman (1979) for the proof of the correspondence. The basic intuition of the proof is worth mentioning, however, and builds on the way NFSAs parse their input. Recall that the difference between NFSA and DFSA is that in an NFSA a state $ q_i $ may have more than one possible next state given an input i (for example $ q_a $ and $ q_b $). The algorithm in Figure 2.21 dealt with this problem by choosing either $ q_a $ or $ q_b $ and then backtracking if the choice turned out to be wrong. We mentioned that a parallel version of the algorithm would follow both paths (toward $ q_a $ and $ q_b $) simultaneously.

The algorithm for converting a NFSA to a DFSA is like this parallel algorithm; we build an automaton that has a deterministic path for every path our parallel recognizer might have followed in the search space. We imagine following both paths simultaneously, and group together into an equivalence class all the states we reach on the same input symbol (i.e., $ q_a $ and $ q_b $). We now give a new state label to this new equivalence class state (for example $ q_{ab} $). We continue doing this for every possible input for every possible group of states. The resulting DFSA can have as many states as there are distinct sets of states in the original NFSA. The number of different subsets of a set with N elements is $ 2^N $, hence the new DFSA can have as many as $ 2^N $ states.

2.3 REGULAR LANGUAGES AND FSAs

As we suggested above, the class of languages that are definable by regular expressions is exactly the same as the class of languages that are characterizable by finite-state automata (whether deterministic or non-deterministic). Because of this, we call these languages the \textit{regular languages}. In order to give a formal definition of the class of regular languages, we need to refer back to two earlier concepts: the alphabet $ \Sigma $, which is the set of all symbols in the language, and the empty string $ \varepsilon $, which is conventionally not included in $ \Sigma $. In addition, we make reference to the empty set $ \emptyset $ (which is distinct from $ \varepsilon $). The class of regular languages (or \textit{regular sets}) over $ \Sigma $ is then formally defined as follows: $ {}^{1} $

1. 0 is a regular language

2. $ \forall a \in \Sigma \cup \varepsilon, \{a\} \text{ is a regular language} $

3. If $ L_{1} $ and $ L_{2} $ are regular languages, then so are:

(a) $ L_1 \cdot L_2 = \{xy \mid x \in L_1, y \in L_2\} $, the concatenation of $ L_1 $.

$$ L_{2} $$

(b) $ L_1 \cup L_2 $, the union or disjunction of $ L_1 $ and $ L_2 $

(c) $ L_{1}^{*} $, the Kleene closure of $ L_{1} $

Only languages which meet the above properties are regular languages. Since the regular languages are the languages characterizable by regular expressions, all the regular expression operators introduced in this chapter (except memory) can be implemented by the three operations which define regular languages: concatenation, disjunction/union (also called “|”), and Kleene closure. For example all the counters (*,+,

{n,m}) are just a special case of repetition plus Kleene *. All the anchors can be thought of as individual special symbols. The square braces [ ] are a kind of disjunction (i.e., [ab] means “a or b”, or the disjunction of a and b). Thus it is true that any regular expression can be turned into a (perhaps larger) expression which only makes use of the three primitive operations.

Regular languages are also closed under the following operations ( $ \Sigma^{*} $ means the infinite set of all possible strings formed from the alphabet $ \Sigma $):

intersection: if $ L_1 $ and $ L_2 $ are regular languages, then so is $ L_1 \cap L_2 $, the language consisting of the set of strings that are in both $ L_1 $ and $ L_2 $.

• difference: if $ L_1 $ and $ L_2 $ are regular languages, then so is $ L_1 - L_2 $, the language consisting of the set of strings that are in $ L_1 $ but not $ L_2 $.

• complementation: If $ L_1 $ is a regular language, then so is $ \Sigma^* - L_1 $, the set of all possible strings that aren't in $ L_1 $.

• reversal: If $ L_1 $ is a regular language, then so is $ L_1^R $, the language consisting of the set of reversals of all the strings in $ L_1 $.

The proof that regular expressions are equivalent to finite-state automata can be found in Hopcroft and Ullman (1979), and has two parts: showing that an automaton can be built for each regular language, and conversely that a regular language can be built for each automaton.

We won't give the proof, but we give the intuition by showing how to do the first part: take any regular expression and build an automaton from it. The intuition is inductive on the number of operators: for the base case we build an automaton to correspond to the regular expressions with no operators, i.e. the regular expressions $ \emptyset $, $ \varepsilon $, or any single symbol $ a \in \Sigma $. Fig. 2.24 shows the automata for these three base cases.

Now for the inductive step, we show that each of the primitive operations of a regular expression (concatenation, union, closure) can be imitated by an automaton:

• concatenation: We just string two FSAs next to each other by connecting all the final states of $ FSA_{1} $ to the initial state of $ FSA_{2} $ by an $ \varepsilon $-transition.

• closure: We create a new final and initial state, connect the original final states of the FSA back to the initial states by $ \varepsilon $-transitions (this implements the repetition part of the Kleene*), and then put direct links between the new initial and final states by $ \varepsilon $-transitions (this implements the possibility of having zero occurrences). We'd leave out this last part to implement Kleene-plus instead.

• union: We add a single new initial state $ q'_{0} $, and add new $ \varepsilon $-transitions from it to the former initial states of the two machines to be joined.

2.4 SUMMARY

This chapter introduced the most important fundamental concept in language processing, the finite automaton, and the practical tool based on automaton, the regular expression. Here's a summary of the main points we covered about these ideas:

• The regular expression language is a powerful tool for pattern-matching.

• Basic operations in regular expressions include concatenation of symbols, disjunction of symbols ( [ ], |, and .), counters (*, +, and {n, m} ), anchors ( ^, $) and precedence operators ( ( , , ) ).

• Any regular expression can be realized as a finite state automaton (FSA).

• Memory (\1 together with ( )) is an advanced operation that is often considered part of regular expressions, but which cannot be realized as a finite automaton.

• An automaton implicitly defines a formal language as the set of strings the automaton accepts.

An automaton can use any set of symbols for its vocabulary, including letters, words, or even graphic images.

• The behavior of a deterministic automaton (DFSA) is fully determined by the state it is in.

• A non-deterministic automaton (NFSA) sometimes has to make a choice between multiple paths to take given the same current state and next input.

• Any NFSA can be converted to a DFSA.

• The order in which a NFSA chooses the next state to explore on the agenda defines its search strategy. The depth-first search or LIFO strategy corresponds to the agenda-as-stack; the breadth-first search or FIFO strategy corresponds to the agenda-as-queue.

• Any regular expression can be automatically compiled into a NFSA and hence into a FSA.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

Finite automata arose in the 1950s out of Turing's (1936) model of algorithmic computation, considered by many to be the foundation of modern computer science. The Turing machine was an abstract machine with a finite control and an input/output tape. In one move, the Turing machine could read a symbol on the tape, write a different symbol on the tape, change state, and move left or right. Thus the Turing machine differs from a finite-state automaton mainly in its ability to change the symbols on its tape.

Inspired by Turing's work, McCulloch and Pitts built an automata-like model of the neuron (see von Neumann, 1963, p. 319). Their model, which is now usually called the McCulloch-Pitts neuron (McCulloch and Pitts, 1943), was a simplified model of the neuron as a kind of "computing element" that could be described in terms

of propositional logic. The model was a binary device, at any point either active or not, which took excitatory and inhibitory input from other neurons and fired if its activation passed some fixed threshold. Based on the McCulloch-Pitts neuron, Kleene (1951) and (1956) defined the finite automaton and regular expressions, and proved their equivalence. Non-deterministic automata were introduced by Rabin and Scott (1959), who also proved them equivalent to deterministic ones.

Ken Thompson was one of the first to build regular expressions compilers into editors for text searching (Thompson, 1968). His editor ed included a command “g/regular expression/p”, or Global Regular Expression Print, which later became the UNIX grep utility.

There are many general-purpose introductions to the mathematics underlying automata theory, such as Hopcroft and Ullman (1979) and Lewis and Papadimitriou (1988). These cover the mathematical foundations of the simple automata of this chapter, as well as the finite-state transducers of Ch. 3, the context-free grammars of Ch. 12, and the Chomsky hierarchy of Ch. 15. Friedl (1997) is a very useful comprehensive guide to the advanced use of regular expressions.

The metaphor of problem-solving as search is basic to Artificial Intelligence (AI); more details on search can be found in any AI textbook such as Russell and Norvig (2002).

EXERCISES

2.1 Write regular expressions for the following languages: You may use either Perl notation or the minimal “algebraic” notation of Sec. 2.3, but make sure to say which one you are using. By “word”, we mean an alphabetic string separated from other words by white space, any relevant punctuation, line breaks, and so forth.

a. the set of all alphabetic strings.

b. the set of all lowercase alphabetic strings ending in a b.

c. the set of all strings with two consecutive repeated words (e.g., “Humbert Humbert” and “the the” but not “the bug” or “the big bug”).

d. the set of all strings from the alphabet $a, b$ such that each $a$ is immediately preceded and immediately followed by $a$ $b$.

e. all strings which start at the beginning of the line with an integer (i.e., 1,2,3,...,10,...,10000,...) and which end at the end of the line with a word.

f. all strings which have both the word grotto and the word raven in them. (but not, for example, words like grottos that merely contain the word grotto).

g. write a pattern which places the first word of an English sentence in a register. Deal with punctuation.

2.2 Implement an ELIZA-like program, using substitutions such as those described on page 10. You may choose a different domain than a Rogerian psychologist, if you wish, although keep in mind that you would need a domain in which your program can legitimately do a lot of simple repeating-back.

2.3 Complete the FSA for English money expressions in Fig. 2.16 as suggested in the text following the figure. You should handle amounts up to $100,000, and make sure that “cent” and “dollar” have the proper plural endings when appropriate.

2.4 Design an FSA that recognizes simple date expressions like March 15, the 22nd of November, Christmas. You should try to include all such “absolute” dates, (e.g. not “deictic” ones relative to the current day like the day before yesterday). Each edge of the graph should have a word or a set of words on it. You should use some sort of shorthand for classes of words to avoid drawing too many arcs (e.g., furniture → desk, chair, table).

2.5 Now extend your date FSA to handle deictic expressions like yesterday, tomorrow, a week from tomorrow, the day before yesterday, Sunday, next Monday, three weeks from Saturday.

2.6 Write an FSA for time-of-day expressions like eleven o'clock, twelve-thirty, midnight, or a quarter to ten and others.

2.7 (Due to Pauline Welby; this problem probably requires the ability to knit.) Write a regular expression (or draw an FSA) which matches all knitting patterns for scarves with the following specification: 32 stitches wide, K1P1 ribbing on both ends, stock-inette stitch body, exactly two raised stripes. All knitting patterns must include a cast-on row (to put the correct number of stitches on the needle) and a bind-off row (to end the pattern and prevent unraveling). Here's a sample pattern for one possible scarf matching the above description.²

1. Cast on 32 stitches. cast on; puts stitches on needle

2. K1 P1 across row (i.e. do (K1 P1) 16 times). K1P1 ribbing

3. Repeat instruction 2 seven more times. adds length

4. K32, P32.

5. Repeat instruction 4 an additional 13 times. adds length

6. P32, P32. raised stripe stitch

7. K32, P32. stockinette stitch

8. Repeat instruction 7 an additional 251 times. adds length

9. P32, P32. raised stripe stitch

10. K32, P32. stockinette stitch

11. Repeat instruction 10 an additional 13 times. adds length

12. K1 P1 across row. K1P1 ribbing

13. Repeat instruction 12 an additional 7 times. adds length

14. Bind off 32 stitches.

binds off row: ends pattern

2.8 Write a regular expression for the language accepted by the NFSA in Fig. 2.28.

Figure 2.28 A mystery language

2.9 Currently the function D-RECOGNIZE in Fig. 2.13 only solves a subpart of the important problem of finding a string in some text. Extend the algorithm to solve the following two deficiencies: (1) D-RECOGNIZE currently assumes that it is already pointing at the string to be checked, and (2) D-RECOGNIZE fails if the string it is pointing includes as a proper substring a legal string for the FSA. That is, D-RECOGNIZE fails if there is an extra character at the end of the string.

2.10 Give an algorithm for negating a deterministic FSA. The negation of an FSA accepts exactly the set of strings that the original FSA rejects (over the same alphabet), and rejects all the strings that the original FSA accepts.

2.11 Why doesn't your previous algorithm work with NFSAs? Now extend your algorithm to negate an NFSA.

Friedl, J. E. F. (1997). Master Regular Expressions. O'Reilly.

Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA.

Kaplan, R. M. and Kay, M. (1994). Regular models of phonological rule systems. Computational Linguistics, 20(3), 331–378.

Kleene, S. C. (1951). Representation of events in nerve nets and finite automata. Tech. rep. RM-704, RAND Corporation. RAND Research Memorandum.

Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. In Shannon, C. and McCarthy, J. (Eds.), Automata Studies, pp. 3–41. Princeton University Press, Princeton, NJ.

Lewis, H. and Papadimitriou, C. (1988). Elements of the Theory of Computation. Prentice-Hall. Second edition.

McCulloch, W. S. and Pitts, W. (1943). A logical calculus of ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5, 115–133. Reprinted in Neurocomputing: Foundations of Research, ed. by J. A. Anderson and E Rosenfeld. MIT Press 1988.

Rabin, M. O. and Scott, D. (1959). Finite automata and their decision problems. IBM Journal of Research and Development, 3(2), 114–125.

Russell, S. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. Second edition.

Thompson, K. (1968). Regular expression search algorithm. Communications of the ACM, 11(6), 419–422.

Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42, 230–265. Read to the Society in 1936, but published in 1937. Correction in volume 43, 544–546.

van Santen, J. P. H. and Sproat, R. (1998). Methods and tools. In Sproat, R. (Ed.), Multilingual Text-To-Speech Synthesis: The Bell Labs Approach, pp. 7–30. Kluwer, Dordrecht.

von Neumann, J. (1963). Collected Works: Volume V. Macmillan Company, New York.

Weizenbaum, J. (1966). ELIZA – A computer program for the study of natural language communication between man and machine. Communications of the ACM, 9(1), 36–45.

WORDS & TRANSDUCERS

How can there be any sin in sincere?

Where is the good in goodbye?

Meredith Willson, The Music Man

Ch. 2 introduced the regular expression, showing for example how a single search string could help us find both woodchuck and woodchucks. Hunting for singular or plural woodchucks was easy; the plural just tacks an s on to the end. But suppose we were looking for another fascinating woodland creatures; let's say a fox, and a fish, that surly peccary and perhaps a Canadian wild goose. Hunting for the plurals of these animals takes more than just tacking on an s. The plural of fox is foxes; of peccary, peccaries; and of goose, geese. To confuse matters further, fish don't usually change their form when they are plural $ ^{1} $.

It takes two kinds of knowledge to correctly search for singulars and plurals of these forms. Orthographic rules tell us that English words ending in -y are pluralized by changing the -y to -i- and adding an -es. Morphological rules tell us that fish has a null plural, and that the plural of goose is formed by changing the vowel.

The problem of recognizing that a word (like foxes) breaks down into component morphemes (fox and -es) and building a structured representation of this fact is called morphological parsing.

Parsing means taking an input and producing some sort of linguistic structure for it. We will use the term parsing very broadly throughout this book, including many kinds of structures that might be produced; morphological, syntactic, semantic, discourse; in the form of a string, or a tree, or a network. Morphological parsing or stemming applies to many affixes other than plurals; for example we might need to take any English verb form ending in -ing (going, talking, congratulating) and parse it into its verbal stem plus the -ing morpheme. So given the surface or input form going, we might want to produce the parsed form VERB-go + GERUND-ing.

Morphological parsing is important throughout speech and language processing. It plays a crucial role in Web search for morphologically complex languages like Russian or German; in Russian the word Moscow has different endings in the phrases Moscow, of Moscow, from Moscow, and so on. We want to be able to automatically

search for the inflected forms of the word even if the user only typed in the base form. Morphological parsing also plays a crucial role in part-of-speech tagging for these morphologically complex languages, as we will see in Ch. 5. It is important for producing the large dictionaries that are necessary for robust spell-checking. We will need it in machine translation to realize for example that the French words va and aller should both translate to forms of the English verb go.

To solve the morphological parsing problem, why couldn't we just store all the plural forms of English nouns and -ing forms of English verbs in a dictionary and do parsing by lookup? Sometimes we can do this, and for example for English speech recognition this is exactly what we do. But for many NLP applications this isn't possible because -ing is a productive suffix; by this we mean that it applies to every verb. Similarly -s applies to almost every noun. Productive suffixes even apply to new words; thus the new word fax can automatically be used in the -ing form: faxing. Since new words (particularly acronyms and proper nouns) are created every day, the class of nouns in English increases constantly, and we need to be able to add the plural morpheme -s to each of these. Additionally, the plural form of these new nouns depends on the spelling/pronunciation of the singular form; for example if the noun ends in -z then the plural form is -es rather than -s. We'll need to encode these rules somewhere.

Finally, we certainly cannot list all the morphological variants of every word in morphologically complex languages like Turkish, which has words like:

(3.1) uygarlaştıramadıklarimizdanmşsinizcasına

uygar +laş +tir +ama +dik +lar +imiz +dan +mis +siniz +casina

civilized +BEC +CAUS +NABL +PART +PL +P1PL +ABL +PAST +2PL +AsIf

"(behaving) as if you are among those whom we could not civilize"

The various pieces of this word (the morphemes) have these meanings:

+BEC “become”

+CAUS the causative verb marker ('cause to X')

+NABL "not able"

+PART past participle form

+P1PL 1st person pl possessive agreement

+2PL 2nd person pl

+ABL ablative (from/among) case marker

+AsIf derivationally forms an adverb from a finite verb

Not all Turkish words look like this; the average Turkish word has about three morphemes. But such long words do exist; indeed Kemal Oflazer, who came up with this example, notes (p.c.) that verbs in Turkish have 40,000 possible forms not counting derivational suffixes. Adding derivational suffixes, such as causatives, allows a theoretically infinite number of words, since causativization can be repeated in a single word (You cause X to cause Y to … do W). Thus we cannot store all possible Turkish words in advance, and must do morphological parsing dynamically.

In the next section we survey morphological knowledge for English and some other languages. We then introduce the key algorithm for morphological parsing, the finite-state transducer. Finite-state transducers are a crucial technology throughout speech and language processing, so we will return to them again in later chapters.

After describing morphological parsing, we will introduce some related algorithms in this chapter. In some applications we don't need to parse a word, but we do need to map from the word to its root or stem. For example in information retrieval and web search (IR), we might want to map from foxes to fox; but might not need to also know that foxes is plural. Just stripping off such word endings is called stemming in IR. We will describe a simple stemming algorithm called the Porter stemmer.

For other speech and language processing tasks, we need to know that two words have a similar root, despite their surface differences. For example the words sang, sung, and sings are all forms of the verb sing. The word sing is sometimes called the common lemma of these words, and mapping from all of these to sing is called lemmatization. $ ^{2} $

Next, we will introduce another task related to morphological parsing. Tokenization or word segmentation is the task of separating out (tokenizing) words from running text. In English, words are often separated from each other by blanks (whitespace), but whitespace is not always sufficient; we'll need to notice that New York and rock 'n' roll are individual words despite the fact that they contain spaces, but for many applications we'll need to separate I'm into the two words I and am.

Finally, for many applications we need to know how similar two words are orthographically. Morphological parsing is one method for computing this similarity, but another is to just compare the strings of letters to see how similar they are. A common way of doing this is with the minimum edit distance algorithm, which is important throughout NLP. We'll introduce this algorithm and also show how it can be used in spell-checking.

3.1 SURVEY OF (MOSTLY) ENGLISH MORPHOLOGY

Morphology is the study of the way words are built up from smaller meaning-bearing units, morphemes. A morpheme is often defined as the minimal meaning-bearing unit in a language. So for example the word fox consists of a single morpheme (the morpheme fox) while the word cats consists of two: the morpheme cat and the morpheme -s.

As this example suggests, it is often useful to distinguish two broad classes of morphemes: stems and affixes. The exact details of the distinction vary from language to language, but intuitively, the stem is the “main” morpheme of the word, supplying the main meaning, while the affixes add “additional” meanings of various kinds.

Affixes are further divided into prefixes, suffixes, infixes, and circumfixes. Prefixes precede the stem, suffixes follow the stem, circumfixes do both, and infixes are inserted inside the stem. For example, the word eats is composed of a stem eat and the suffix -s. The word unbuckle is composed of a stem buckle and the prefix un-. English doesn't have any good examples of circumfixes, but many other languages do. In German, for example, the past participle of some verbs is formed by adding ge- to the beginning of the stem and -t to the end; so the past participle of the verb sagen (to say) is gesagt (said). Infixes, in which a morpheme is inserted in the middle of a word,

occur very commonly for example in the Philippine language Tagalog. For example the affix um, which marks the agent of an action, is infixed to the Tagalog stem hingi “borrow” to produce humingi. There is one infix that occurs in some dialects of English in which the taboo morphemes “fking” or “bldy” or others like them are inserted in the middle of other words (“Man-fking-hattan”, “abso-bldy-lutely”³) (McCawley, 1978).

A word can have more than one affix. For example, the word rewrites has the prefix re-, the stem write, and the suffix -s. The word unbelievably has a stem (believe) plus three affixes (un-, -able, and -ly). While English doesn't tend to stack more than four or five affixes, languages like Turkish can have words with nine or ten affixes, as we saw above. Languages that tend to string affixes together like Turkish does are called agglutinative languages.

There are many ways to combine morphemes to create words. Four of these methods are common and play important roles in speech and language processing: inflection, derivation, compounding, and cliticization.

Inflection is the combination of a word stem with a grammatical morpheme, usually resulting in a word of the same class as the original stem, and usually filling some syntactic function like agreement. For example, English has the inflectional morpheme -s for marking the plural on nouns, and the inflectional morpheme -ed for marking the past tense on verbs. Derivation is the combination of a word stem with a grammatical morpheme, usually resulting in a word of a different class, often with a meaning hard to predict exactly. For example the verb computerize can take the derivational suffix -ation to produce the noun computerization. Compounding is the combination of multiple word stems together. For example the noun doghouse is the concatenation of the morpheme dog with the morpheme house. Finally, cliticization is the combination of a word stem with a clitic. A clitic is a morpheme that acts syntactically like a word, but is reduced in form and attached (phonologically and sometimes orthographically) to another word. For example the English morpheme 've in the word I've is a clitic, as is the French definite article l' in the word l'opera. In the following sections we give more details on these processes.