Preparatory assignments

Automata and Grammars

1. Install one of the available toolkits for working with Finite State Transducers (FST) on your computer.
   • Linux: Stuttgart Finite State Toolkit (recommended)
   • Windows: Xerox Finite State Toolkit
2. Recall basic notions of
   • Finite State Machines (FSM)
     • states and transitions
     • state transition tables and state transition diagrams
     • deterministic vs. nondeterministic FSMs
   • Regular expressions
     • sequence, alternative, quantification (repetition, enumeration)
   • Regular grammars and regular languages
     • rewrite rules
     • operations on regular languages and their closure properties
     • Chomsky hierarchy
3. Find out the relationships between Finite state machines, regular expressions, regular grammars and regular languages
4. Many cultures around the world structure their songs and instrumentals as a playful call-and-response dialogue, which is particularly characteristic for the music of Africa.
   • Implement a finite state machine for valid sequence of calls (C) and responses (R). Display your solution as a state transition table, a state transition diagram, a regular expression and a regular grammar.
   • Is the language accepted by your machine a finite one? Is your automaton deterministic?
5. The blues pattern is a very influential traditional system of chord progression in popular music which comes in various flavours, e.g. as one of the many variants of a 8-bar, 12-bar or 16-bar blues pattern.
   • Implement one of the possible chord sequences as a finite state machine, for instance my favorite: C C C C | F F C C | G G F F | C C C G | ...
   • Is the language accepted by your automaton a finite one? Is your automaton deterministic?
6. Implement an automaton that accepts all personal pronouns of your mother tongue, e.g. as given here for Amharic.
   • Is the language accepted by your automaton a finite one? Is your automaton deterministic?
   • Is the automaton sound, i.e. does it accept only valid personal pronouns of your language? Is it complete, i.e. does it accept all the personal pronouns of your language? If not, count the number of false positives and/or false negatives.
   • How many states has your automaton. Is there still room for minimization?
7. Recall basic notions of Finite State Transducers (FST)
   • Similarities and differences between FSMs and FSTs
   • Moore vs. Mealy automata
   • Operations on FSTs (in particular: union, concatenation, composition)
8. Find an example of a character sequence which can be better modelled with a non-deterministic automaton than with deterministic one. Do such cases occur in your language?
9. Find an example of a a character sequence which cannot be modelled with a Finite State Machine? Do such cases occur in your language?

Probability

1. Recall the notion of discrete probability and discrete probability distribution. Estimate the probability distribution for the characters in a short text of your mother tongue. How many zero-probabilities did you encounter?
2. Recall the notion of conditional probability and conditional probability distribution. Estimate a small part of the conditional probability distribution for the characters in your text, given the immediately preceding character. Give some examples of zero probabilities. Distinguish between successive character pairs that are impossible in your language and others, which are possible, but not occurring in your text.
3. Calculate from the above estimations the probability of the occurrence of a two-character sequence. Which assumptions do you have to make, in order to be able to do so?
4. Calculate from the above estimations the probability of the occurrence of a three-character sequence. Which assumptions do you have to make, in order to be able to do so?
5. Can you compute the probability of a word based solely on the above estimations?