L2 Finite-State Automata, Transducers, and Morphology

[T2] What are the main topics of Lecture 2?

Background FSA/RegExp knowledge, English morphology, FSAs for recognizing English words, FSTs for parsing/generating English words, and why finite-state methods are still useful.

[T2] What does Q represent in a finite state automaton (FSA)?

The finite set of states.

[T2] What does q0 represent in an FSA?

The start state.

[T2] What does F represent in an FSA?

The set of final/accepting states.

[T2] What does Σ represent in an FSA?

The alphabet/set of input symbols.

[T2] What does the transition relation of the lecture's FSA map?

Q × Σ → 2^Q.

[T2] Why does the FSA transition relation map to 2^Q?

A state-symbol pair may correspond to a set of possible next states.

[IT2 p.10] IMAGE: Basic Finite State Automaton

Be able to identify the states Q, start state q0, final state(s) F, alphabet Σ, transitions, loops, and failure state from the diagram.

[A2] In an FSA diagram, how is the start state indicated?

By an incoming arrow from outside the automaton.

[A2] In an FSA diagram, how is a final/accepting state indicated?

By a double circle.

[A2] What does an edge labeled with a symbol in an FSA mean?

If that symbol is read in the source state, the automaton may follow that transition to the destination state.

[A2] What does a self-loop in an FSA mean?

Reading the indicated symbol can leave the automaton in the same state.

[T2] When does an FSA accept an input string?

When the symbols can be processed along valid transitions and the machine finishes in a final/accepting state.

[T2] When does an FSA reject an input string?

When no valid transition/path remains or the input finishes without reaching an accepting state.

[IT2 p.21] IMAGE: FSA string tracing examples

Be able to trace the input one symbol at a time and determine why one example is rejected and another is accepted.

[A2] What procedure should you use to determine whether an FSA accepts a string?

Start at q0, process symbols from left to right by following valid transitions, and check whether the completed path ends in an accepting state.

[A2] If processing an input symbol sends the machine to a failure state, what happens?

That path cannot accept the input.

[T2] What are regular expressions used for in the lecture?

Searching for, recognizing, and editing patterns in text.

[A2] What strings does /CPSC4[0-9][0-9][A-Z]*/ describe?

Strings beginning with CPSC4, followed by two digits, followed by zero or more capital letters.

[A2] What does [0-9] mean in a regular expression?

Any digit from 0 through 9.

[A2] What does [A-Z] mean in a regular expression?

Any uppercase English letter.

[A2] What does * mean in the regex example [A-Z]*?

Zero or more occurrences of the preceding pattern.

[A2] What does /[1-2][0-9]{3}/ match?

A four-digit sequence beginning with 1 or 2.

[A2] What does {3} mean in a regex?

Exactly three repetitions of the preceding pattern.

[T2] What was the goal of the lecture's “the” regex example?

Find all instances of the determiner “the” in an English text, such as for counting or substitution.

[A2] Why is /the/ a bad regex for finding the determiner “the”?

It also matches the character sequence “the” inside other words, producing false positives.

[A2] In “The other cop went to the bank but there were no people there,” why does /the/ create false positives?

It matches occurrences inside words such as “other” and “there,” not just the determiner “the.”

[T2] What precision did /the/ obtain in the lecture's example?

1/4.

[A2] What improvement was made in the second regex attempt?

/\bthe\b/ was used so “the” had to occur at word boundaries.

[A2] What does \b accomplish in /\bthe\b/?

It restricts the match to a word boundary, preventing “the” from matching inside larger words.

[A2] Why does /\bthe\b/ still have a false negative in the lecture's example?

It misses capitalized “The” at the beginning of the sentence.

[T2] What precision did /\bthe\b/ obtain in the lecture example?

1.

[T2] What recall did /\bthe\b/ obtain in the lecture example?

1/2.

[A2] How was the capitalization problem fixed?

By using /\b[Tt]he\b/.

[A2] What does [Tt] mean in /\b[Tt]he\b/?

The first character can be either uppercase T or lowercase t.

[T2] What precision and recall did /\b[Tt]he\b/ obtain in the lecture example?

Precision = 1 and recall = 1.

[A2] What does the substitution expression s/\b([tT]he

[Aa]n?)\b/DET/ do?

[A2] In ([tT]he

[Aa]n?), what does

[A2] In [Aa]n?, what does ? mean?

The n is optional, allowing both “a” and “an.”

[F2] What broad relationship does the lecture emphasize between regular expressions and FSAs?

They are closely related finite-state ways of describing and implementing recognizable patterns.

[IF2 p.35] IMAGE: Relationship between RegExp, FSA, and linguistic phenomena

Recognize that finite-state machinery can model linguistic phenomena and that RegExp/FSA descriptions are closely related.

[T2] What is morphology?

The study of how words are formed from minimal meaning-bearing units called morphemes.

[T2] Is morphology language-specific?

Yes; morphological systems differ across languages.

[T2] What two broad classes of morphemes does the lecture distinguish?

Stems and affixes.

[T2] What is a stem?

The core meaning-bearing unit of a word.

[T2] What is an affix?

A piece attached to a stem that changes its meaning and/or grammatical function.

[A2] How is “unhappily” segmented in the lecture?

un + happy + ly.

[T2] What are the two broad classes of English morphology introduced in Lecture 2?

Inflectional morphology and derivational morphology.

[T2] What is the defining property of inflectional morphology regarding word class?

The resulting word has the same word class as the original.

[T2] What does inflectional morphology change if it usually preserves word class?

It gives the word a different grammatical or semantic function/form.

[T2] What inflectional morphology is shown for nouns?

Plural and possessive marking.

[A2] Give the lecture's noun plural example.

cat → cats.

[A2] Give the lecture's noun possessive example.

cat → cat’s.

[T2] What inflectional morphology is shown for verbs?

Markers for tense and person.

[A2] Give the lecture's tense example.

walk → walked.

[A2] Give the lecture's person/agreement example.

walk → walks.

[T2] What inflectional morphology is shown for adjectives?

Comparative and superlative marking.

[A2] Give the lecture's comparative example.

tall → taller.

[A2] Give the lecture's superlative example.

tall → tallest.

[T2] What are morphological irregulars?

Words whose inflected forms do not follow the regular rules.

[A2] Give the lecture's irregular noun examples.

mouse/mice, goose/geese, ox/oxen.

[A2] What forms of “eat” illustrate irregular verb morphology?

eat, eats, eating, ate, eaten.

[A2] What forms of “catch” illustrate irregular verb morphology?

catch, catches, catching, caught, caught.

[A2] What forms of “cut” illustrate irregular verb morphology?

cut, cuts, cutting, cut, cut.

[T2] What is the major characteristic of derivational morphology emphasized in the lecture?

It can change a word's word class.

[T2] What is nominalization?

Deriving a noun from a verb or adjective.

[A2] What derivational suffix turns “computerize” into “computerization”?

-ation.

[A2] What derivational suffix turns “appoint” into “appointee”?

-ee.

[A2] What derivational suffix turns “kill” into “killer”?

-er.

[A2] What derivational suffix turns “fuzzy” into “fuzziness”?

-ness.

[A2] What derivational suffix turns “computation” into “computational”?

-al.

[A2] What derivational suffix turns “embrace” into “embraceable”?

-able.

[A2] What derivational suffix turns “clue” into “clueless”?

-less.

[T2] What category change is illustrated by -al, -able, and -less?

Noun/verb → adjective.

[T2] What does the lecture say about derivation with the suffix -ant?

It is less productive and forms nouns only with certain verbs of Latin origin.

[A2] What examples of -ant derivation are given?

assistant, consultant, servant.

[T2] What is Goal #1 of using FSAs for morphology?

Recognize whether a string is an English word.

[T2] Why can't we simply check whether every valid English word is in a dictionary?

The dictionary contains base forms, while morphology produces many additional inflected forms.

[T2] What is morphotactics?

The rules governing the ordering of affixes in a language.

[T2] What two-step plan does the lecture give for using FSAs to recognize morphologically valid words?

First capture morphotactics; then add the actual stems.

[IT2 p.60] IMAGE: FSA for Noun Inflectional Morphology

Understand paths for regular singular nouns, regular plural nouns, irregular singular nouns, and irregular plural nouns.

[A2] In the noun inflection FSA, how can a regular singular noun be accepted?

Follow the regular-noun path to the singular accepting state without taking the plural -s transition.

[A2] In the noun inflection FSA, how is a regular plural formed?

Follow the regular-noun path and then the plural (-s) transition.

[A2] Why can an irregular plural noun take a different path from a regular noun?

Its plural form is stored/recognized directly rather than being generated by simply adding regular -s.

[IF2 p.62] IMAGE: FSA after adding actual stems

Recognize how stem spellings can be expanded into paths in the automaton; do not memorize the entire network.

[T2] What important English plural spelling rules are NOT captured by the simple stem FSA?

Nouns ending in s, z, sh, ch, or x take -es; consonant + y changes before plural formation.

[IT2 p.63] IMAGE: Derivational morphology FSA

Be able to follow possible derivational paths and recognize how suffixes can change word class.

[A2] In the derivational morphology FSA, what does a transition such as -ize/V indicate?

Adding -ize produces or moves to a verb category.

[A2] In the derivational morphology FSA, what does a transition such as -ation/N indicate?

Adding -ation produces or moves to a noun category.

[A2] In the derivational morphology FSA, what does -ly/Adv indicate?

Adding -ly produces an adverb.

[IT2 p.64] IMAGE: Highlighted derivational path

Determine which word corresponds to the highlighted path through the derivational FSA.

[A2] In the page 64 highlighted-path example, which answer corresponds to the highlighted path?

formally.

[T2] What are the three computational morphology tasks listed in the lecture?

Recognition, parsing/generation, and stemming.

[T2] What is morphological recognition?

Determining whether a string is a valid word/form.

[T2] What is morphological parsing?

Mapping a surface word to its stem, word class, and lexical/morphological features.

[T2] What is morphological generation?

Mapping a lexical representation containing a stem/class/features to a surface word.

[A2] What two analyses can the word “lies” have in the lecture?

lie +N +PL and lie +V +3SG.

[A2] What does “foxes” parse to in the lecture's morphology task?

fox +PL.

[A2] What does “cat” parse to in the lecture's morphology task?

cat +SG.

[T2] What is the purpose of stemming in the lecture's computational morphology tasks?

Reduce a word to its stem.