Mikołaj Bojańczyk

In the following we write \field to denote any field, but of course the example of the real numbers is the most natural one. Fix the field \field for the rest of the lecture.

weighted automaton consists of the following ingredients:
• an input alphabet, which is a set \Sigma;
• a set Q of states, which is a vector space over \field;
• an initial state q_0 \in Q;
• for each letter a \in \Sigma, a linear transition function \delta_a : Q \to Q;
• a linear output function F : Q \to \field.

An automaton is called finite if the input alphabet has finitely many elements and the vector space has finite dimension.

(One could consider a slightly more uniform and general definition, where the input alphabet is also a vector space, and the transition function is a linear map Q \times \Sigma \to Q. The case of finite input alphabets would be recovered by viewing an input letter as one of the base vectors in the vector space \field^\Sigma of finite dimension.)

The semantics if a weighted automaton is a function \Sigma^* \to \field defined as follows. When given an input word, the automaton begins in the initial state q_0. Then for every new input letter a, it applies the transition function \delta_a to the current state, yielding a new state. Finally, it applies the output function F to the state at the end, yielding an element of the underlying field. 

Example. A normal DFA with n states can be viewed as a special case of a weighted automaton. The set of stats will be \field^n, and the reachable ones will only be vectors which have zero on all coordinates except the coordinate corresponding to the current state. \Box

In this lecture, we make the following points:

  1. Weighted automata admit minimisation;
  2. For finite automata, some questions are decidable;
  3. For finite automata, some questions are undecidable.

 

 

Leave a Reply

Your email address will not be published.