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

A weighted automaton consists of the following ingredients:
• an input alphabet, which is a set ;
• a set of states, which is a vector space over ;
• an initial state ;
• for each letter , a linear transition function ;
• a linear output function .

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 . The case of finite input alphabets would be recovered by viewing an input letter as one of the base vectors in the vector space of finite dimension.)

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

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

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.