List of Figures

• NLP layers
• Sample finite-state automaton
• Deterministic version of the sample automaton
• Useful version of the sample deterministic automaton
• Classical minimal deterministic acyclic FSA and the corresponding FSA with final transitions
• Simple transducer (adopted from [RS95])
• Subsequential transducer - a transformation of the transducer from fig.  (taken from [RS95])
• Morphology of spała as a path in a transducer. Categories kept to a minimum due to lack of space (only part-of-speech)
• Transducer input data for "spała"
• Format of input data for "spała" for a simple automaton - acceptor
• Prefixes inflate automata by enforcing storing lexemes in full form
• Coded prefix in data for morphological analysis with automata - acceptors
• Coded infix in morphological data
• Removable prefix coding in an automaton for morphological analysis
• Input data for "spała" for a morphological guesser
• Input data for "szybszy" for a morphological guesser
• Input data for "najszybszy" for a morphological guesser
• Coded infixes in data for a morphological guesser
• The family trees of finite automata constructions taken from [Wat93a] with modifications. Solid edges denote refinements of the solution (and therefore explicit relationships between constructions). They are labeled with the name of the refinement
• A trie whose language is the French regular endings of verbs of the first group
• The unique minimal DAFSA whose language is the French regular endings of verbs of the first group
• Incremental construction algorithm for sorted data
• Examples of construction process for sorted data
• The result of adding the word bae to a minimized automaton containing abd and bad. The automaton inadvertently contains abe as well.
• Incremental construction algorithm from data in arbitrary order
• Examples of Construction process from unsorted data: changes propagate to the root
• Examples of construction process from unsorted data: cloning
• Example automaton from fig.  represented by lists
• Compression of a sparse table (adopted from [TY79])
• Spelling correction with finite-state automata
• Spelling correction with finite-state automata with modifications
• Restoration of diacritics with finite-state automata
• Morphological analysis with transducers
• Morphological analysis with automata-acceptors
• Morphological analysis of unknown words
• Guessing the categories of words. Prefixes and lexemes not present
• Sample deterministic finite-state automaton implementing perfect hashing

Software at http://www.pg.gda.pl/~jandac/fsa.html