Syntactic weighted automata

Mikołaj Bojańczyk

zajęcia / courses

In this part of the lecture, we prove a Myhill-Nerode style theorem for weighted automata, which says that for every weighted automaton, there is a canonical one that recognises the same language, and is minimal in a certain sense. One way of stating the minimality condition is to use homomorphisms of weighted automata, as defined below.

Homomorphisms of weighted automata. Suppose that we have two weighted automata $\Aa$ and $\Aa'$ over the same input alphabet $\Sigma$ . A homomorphism from $\Aa$ to $\Aa'$ is defined to be a linear function $h$ from the state space of $\Aa$ , call it $Q$ , to the state space of $\Aa'$ , call it $Q'$ , which is consistent with the structure of the two automata, in the following sense. The initial state of $\Aa$ is mapped to the initial state of $\Aa'$ , and the following diagrams commute for every $a \in \Sigma$

$\xymatrix{ Q \ar[dr]^{F} \ar[d]_h \\ Q' \ar[r]_{F'} & \field} \qquad \xymatrix{ Q \ar[r]^{\delta_a} \ar[d]_h & Q \ar[d]^h \\ Q' \ar[r]_{\delta'_a} & Q'}$

where $F,F'$ are the output functions of the respective automata, and $\delta_a,\delta'_a$ are the transition functions.

If there is such a homomorphism, then the functions computed by the two automata are the same, as can be shown by induction on the length of the input word. An isomorphism is a homomorphism whose inverse is also a homomorphism. It is not difficult to show that if a homomorphism is a bijection, as a function on state spaces, then it is an isomorphism.

We now state the minimisation theorem for weighted automata. Call an automaton reachable if every state in its state space is a finite linear combination of reachable states, i.e. states that can be reached by reading input words.

Theorem. Let $f : \Sigma^* \to \field$ be a function computed by a weighted automaton. There exists a weighted automaton, called the syntactic automaton of $f$ , which computes $f$ and such that every reachable weighted automaton computing $f$ admits a homomorphism into the syntactic automaton.

Proof. The proof is essentially the same as for the classical Myhill-Nerode theorem.

Define the continuation of a word $w \in \Sigma^*$ to be the function

$v \mapsto f(wv),$

which we will denote by $[w]$ . Before defining the syntactic automaton, we define a bigger automaton, called the continuation automaton. States of the continuation automaton are vectors in $\Sigma^* \to \field$ , which is a vector space, albeit of infinite dimension. The initial state is the continuation of the empty word. The output function maps a state to its value on the empty word. The transition function

$\delta_a : \field^{\Sigma^*} \to \field^{\Sigma^*}$

is simply a permutation of coordinates:

$\delta_a (q) (v) = q(av)$

It is easy to see that this function is linear, and that it maps a continuation $[w]$ to the continuation $[wa]$ . Note how the choice of the function $f$ only plays a role in the definition of the initial state of the automaton.

Define the syntactic automaton to be the continuation automaton with the state space restricted to finite linear combinations of continuations. We need to show that this automaton is well-defined, i.e. the transition functions stay within the state space. This is because the transition functions are linear, and they map continuations to continuations.

We now show that every reachable weighted automaton recognising $f$ admits a homomorphism into the syntactic automaton. Let $\Aa$ be be such a weighted automaton, and let $Q$ be its states. We first show that there is a homomorphism into the continuation automaton, and then we show that the image of the homomorphism is actually the syntactic automaton. Define a function

$h : Q \to \field^{\Sigma^*}$

which maps a state $q$ to the function that maps $w$ to the value of the automaton $\Aa$ after reading $w$ , assuming that the initial state was changed to $q$ . This is clearly a linear function, and it is not difficult to see that it is a homomorphism.

It remains to show that the image of $h$ is actually the syntactic automaton. Since any homomorphism maps reachable states to reachable states, it follows that the image of $h$ is included in the states of the syntactic automaton (because of the assumption that $\Aa$ was reachable). Finally, the homomorphism $h$ has the property that if $w$ is an input word, then the state of $\Aa$ after reading $w$ is mapped to the continuation $[w]$ , and therefore $h$ is surjective. $\Box$

zajęcia / courses

Syntactic weighted automata

Syntactic weighted automata

Leave a Reply