INTR TO COMPUT LING
INTR TO COMPUT LING LING 472
Popular in Course
Popular in Linguistics
This 19 page Class Notes was uploaded by Kurtis Spencer I on Wednesday September 9, 2015. The Class Notes belongs to LING 472 at University of Washington taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/192184/ling-472-university-of-washington in Linguistics at University of Washington.
Reviews for INTR TO COMPUT LING
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/09/15
April 7 2008 Finite State Morphological Parsing Overview Announcements Assignment 1 Morphology primer Overview Finite state methods in morphology Using FSAs to recognize morphologically complex words F STs de nition cascading composition F STs for morphological parsing Morphology A Primer 12 Words consist of stems and af xes A ixes may be pre xes su ixes circum xes or in xes Examples Also root and pattern morphology Examples Phonological processes can sometimes apply to combinations of morphemes Morphology A Primer 22 Languages vary in the richness of their morphological systems Languages also vary in the extent to which phonological processes apply at and sometimes blur morpheme boundaries English has relatively little in ectional morphology but fairly rich if not perfectly productive derivational morphology Turkish has more than 200 billion word forms Bottom line We ll want to be able to parse words morphologically for reasons of linguistic interest as well as practical considerations Morphological Parsing What and Why Examples of morphologically complex words Examples of phonologically blurred morphological boundaries What underlying representations might we want Why would we want to get to those underlying representations How do things change when we consider orthography rather than phonology Overview Finite state methods for morphology Morphotactics morpheme order selection FSAs Morpheme glosses F STs Morphophonology FSTs all in one feel swoop composition Using FSAS to recognize morphological complex words a Concatenate FSAs for rootsstems with F SAs for a ixes Develop with word classes as standins for lists of words a Allow optional multiple a ixes end states with arcs leading out Using FSAS to recognize in ected words 0 Why are there two end states in Figure 32 p67 0 Why are there two arcs labeled regverbstem in Fig 33 Using F SAS to recognize derivational morphology What sequence of states would the FSA in Fig 34 p68 follow to recognize uncoolest What sequence of states would the FSA in Fig 34 p68 follow to recognize unbiggest overgeneration o What sequence of states would the FSA in Fig 35 p69 follow as it tries to recognize unbiggest 0 Why do er and est show up on two different arcs in Fig 35 And a few more notes a BampK state that FSAs and FSTs a very ef cient at storing data Why a BampK state that FSAsF STs are very e icient for processing inputs Why 10 Regular Relations Regular language a set of strings Regular relation a set of tuples of strings Binary regular relation a set of pairs of strings Can be recognized by nite state transducers ll F in ireS tare Transducers Like FSAs but with more than one tape De ne regular relations mappings between sets of strings Can be used to recognize generate translate or relate sets Examples 12 F MiteState Transducers Mealy machines Q a nite set ofstates q0q1 qN Z a nite alphabet of complex symbols 239 0 such that 2396 I ando E O E Q I x O I andOmay each include 6 go the start state F the set of nal states F Q Q 6 1239 0 the transition matrix 13 FSTS Nonlinguistic example Fatherof relation lt Suku Vijay gt lt Jim Emily gt lt Vijay Toby gtlt Vijay Rafe gt Parentof relation lt Suku Vijay gt lt Jim Emily gt lt Vijay Toby gtlt Vijay Rafe gtlt Vanaja Vijay gt lt Sheila Emily gt lt Emily Toby gtlt Emily Rafe gt Grandfatherof relation lt Suku Toby gt lt Suku Rafe gt lt Jim Toby gt lt Jim Rafe gt Muthachanof relation lt Suku Toby gt lt Suku Rafe gt 14 Composing FSTS 12 If the lower tape of one machine and the upper tape of the other can be aligned then go straight from the upper tape of T1 to the lower tape of T2 Composing is equivalent to cascading different from compiling R1 R2 513 z Elyltazygt E R1ampltyzgt E R2 Grandfatherof Fatherof Parentof Order matters Grandfatherof 75 Parentof F atherof 15 Composing FSTS 22 0 Given automata T1 and T2 with state sets Q1 and Q2 and transition functions 61 and 62 o Create set ofpossible states 93 y a 6 Q1 y 6 Q2 o De ne new transition function 63asayai 0 5341 if Elc such that 61asaz39 c 93 and 62ya c o yb 16 FSTS Notjustfancy FSAS Regular languages are closed under difference complementation and intersection regular relations are not Regular languages and regular relations are both closed under union Regular relations are closed under composition and inversion not de ned for regular languages ltabcgt7 aebzc 7 azcezb l7 An FST to parse English nouns Tnum Fig 39 p74 parses the same set of nouns that the F SA in 32 recognizes Why does it have more states What are its input and output alphabets The lexicon given for 39 has a funny spelling for only two words Why 18 Overview Morphology primer Using FSAs to recognize morphologically complex words F STs de nition cascading composition F STs for morphological parsing Next time Spelling change rules lexiconfree morphological analysis ambiguity l9