CMSC 723 / LING 645: Intro to Computational LinguisticsMore about FSAsRecognition using NFSAsNFSA Recognition of “baaa!”Breadth-first Recognition of “baaa!”Regular languagesConcatenationKleene ClosureUnionMorphologySlide 11Phonology and MorphologySyntax and MorphologyTopology of MorphologiesConcatenative MorphologyTemplatic MorphologyTemplatic Morphology: Root MeaningDerivational vs. InflectionalDerivational morphologyInflectional morphologyNouns and Verbs (in English)Regulars and IrregularsRegular (English) VerbsPowerPoint Presentation“To love” in SpanishComputational MorphologySlide 27Building a Morphological ParserLexicon-only MorphologySlide 30Lexicon and Rules: FSA Inflectional Noun MorphologyLexicon and Rules: FSA English Verb Inflectional MorphologyFSA for Derivational Morphology: Adjectival FormationMore Complex Derivational MorphologyUsing FSAs for Recognition: English Nouns and their InflectionMorphological ParsingTerminology for PC-KimmoFour-Fold View of FSTsNominal Inflection FSTLexical and Intermediate TapesSpelling RulesChomsky and Halle NotationIntermediate-to-Surface TransducerState Transition TableTwo-Level MorphologySample RunFSTs and ambiguityWhat to do about Global Ambiguity?Slide 49Slide 50Readings for next timeCMSC 723 / LING 645: Intro to Computational LinguisticsSeptember 15, 2004: DorrMore about FSA’s, Finite State Morphology (J&M 3)Prof. Bonnie J. DorrDr. Christof MonzTA: Adam LeeMore about FSAsTransducersEquivalence of DFSAs and NFSAsRecognition as search: depth-first, breadth-searchRecognition using NFSAsNFSA Recognition of “baaa!”Breadth-first Recognition of “baaa!”should be q2Regular languagesRegular languages are characterized by FSAsFor every NFSA, there is an equivalent DFSA.Regular languages are closed under concatenation, Kleene closure, union.ConcatenationKleene ClosureUnionMorphologyDefinitions and Problems–What is Morphology?–Topology of MorphologiesApproaches to Computational Morphology–Lexicons and Rules–Computational Morphology ApproachesMorphologyThe study of the way words are built up from smaller meaning units called MorphemesSyntaxLexeme/Inflected LexemeGrammars sentencesMorphologyMorpheme/AllomorphMorphotactics wordsPhonologyPhoneme/AllophonePhonotactics lettersAbstract versus Realized HOP +PAST  hop +ed  hopped  /hapt/Phonology and MorphologyPhonology vs. OrthographyHistorical spelling–night, nite –attention, mission, fishScript Limitations–Spoken English has 14 vowels•heed hid hayed head had hoed hood who’d hide how’d taught Tut toy enough–English Alphabet has 5•Use vowel combinatios: far fair fare•Consonantal doubling (hopping vs. hoping)Syntax and MorphologyPhrase-level agreement–Subject-Verb •John studies hard (STUDY+3SG)–Noun-Adjective•Las vacas hermosasSub-word phrasal structures–שברפסיונ–ש+ב+רפס+םי+ונ–That+in+book+PL+Poss:1PL–Which are in our booksconjprepnounposspluralarticleTopology of MorphologiesConcatenative vs. TemplaticDerivational vs. InflectionalRegular vs. IrregularConcatenative MorphologyMorpheme+Morpheme+Morpheme+…Stems: also called lemma, base form, root, lexeme– hope+ing  hoping hop  hoppingAffixes–Prefixes: Antidisestablishmentarianism–Suffixes: Antidisestablishmentarianism–Infixes: hingi (borrow) – humingi (borrower) in Tagalog–Circumfixes: sagen (say) – gesagt (said) in GermanAgglutinative Languages–uygarlaştıramadıklarımızdanmışsınızcasına–uygar+laş+tır+ama+dık+lar+ımız+dan+mış+sınız+casına–Behaving as if you are among those whom we could not cause to become civilizedTemplatic MorphologyRoots and PatternsمتكوببK T B?و مم??كتתכובב?ו ??כתmaktuubwrittenktuuvwrittenTemplatic Morphology: Root MeaningKTB: writing “stuff”בתכבתכמבתכביתכspellingתבותכaddressبتكتاكببوتكمباتكbookةبتكمlibraryبتكمofficewritewriterlette rDerivational vs. InflectionalWord Classes–Parts of speech: noun, verb, adjectives, etc.–Word class dictates how a word combines with morphemes to form new wordsDerivational morphologyNominalization: computerization, appointee, killer, fuzzinessFormation of adjectives: computational, clueless, embraceableCatVar: Categorial Variation Databasehttp://clipdemos.umiacs.umd.edu/catvar/Inflectional morphologyAdds: Tense, number, person, mood, aspectWord class doesn’t changeWord serves new grammatical roleFive verb forms in EnglishOther languages have (lots more)Nouns and Verbs (in English)Nouns have simple inflectional morphology–cat–cat+s, cat+’sVerbs have more complex morphologyRegulars and IrregularsNouns–Cat/Cats–Mouse/Mice, Ox, Oxen, Goose, GeeseVerbs–Walk/Walked–Go/Went, Fly/FlewRegular (English) VerbsMorphological Form Classes Regularly Inflected VerbsStem walk merge try map-s form walks merges tries maps-ing form walking merging trying mappingPast form or –ed participle walked merged tried mappedIrregular (English) VerbsMorphological Form Classes Irregularly Inflected VerbsStem eat catch cut-s form eats catches cuts-ing form eating catching cuttingPast form ate caught cut-ed participle eaten caught cut“To love” in SpanishComputational MorphologyFinite State Morphology–Finite State Transducers (FST)Input/OutputAnalysis/GenerationComputational MorphologyWORD STEM (+FEATURES)*cats cat +N +PLcat cat +N +SGcities city +N +PLgeese goose +N +PLducks (duck +N +PL) or(duck +V +3SG)merging merge +V +PRES-PARTcaught (catch +V +PAST-PART) or (catch +V +PAST)Building a Morphological ParserThe Rules and the Lexicon–General versus Specific–Regular versus Irregular–Accuracy, speed, space–The Morphology of a language Approaches–Lexicon only–Lexicon and Rules•Finite-state Automata•Finite-state Transducers–Rules onlyLexicon-only Morphologyacclaim acclaim $N$acclaim acclaim $V+0$acclaimed acclaim $V+ed$acclaimed acclaim $V+en$acclaiming acclaim $V+ing$acclaims acclaim $N+s$acclaims acclaim $V+s$acclamation acclamation $N$acclamations acclamation $N+s$acclimate acclimate $V+0$acclimated acclimate $V+ed$acclimated acclimate $V+en$acclimates acclimate $V+s$acclimating acclimate $V+ing$• The lexicon lists all surface