carmel-tutorial.rtf

A Primer on Finite State Software for Natural Language Processing Kevin Knight and Yaser Al Onaizan, August 1999 Summary In many practical NLP systems, a lot of useful work is done with finite state devices. This primer covers basic finite state techniques with examples and laboratory software called Carmel (downloadable from http://www.isi.edu/licensed sw/carmel ). Contents 1. Finite State Acceptors 2. Finite State Transducers 3. Probabilistic Acceptors and Transducers 4. Noisy Channel Decoding 5. Acquiring Probabilities from Data ====================================================== 1. Finite State Acceptors A finite state acceptor (FSA) is a network of states and transitions . Each transition has a label . For our purposes, we will assume that an acceptor has exactly one start and exactly one final statestate (which may be the same). A string is an ordered sequence of symbols drawn from a finite vocabulary. An FSA accepts a string w1, w2 ... wn if you can trace a path from the start state to the final state along transitions labeled w1, w2, ... wn. Here is an FSA that accepts three distinct strings: he saw me ran home she talked The software we use has a special representation for writing down this FSA: %%%%%% Filename: fsa1 %%%%%% 3 (0 (1 "he")) (1 (2 "saw")) (2 (3 "me")) (1 (4 "ran")) (4 (3 "home")) (0 (5 "she")) (5 (3 "talked")) The first line gives the name of the final ...