  We show that weighted automata over the field of two elements can be
exponentially more compact than non-deterministic finite state automata. To
show this, we combine ideas from automata theory and communication complexity.
However, weighted automata are also efficiently learnable in Angluin's minimal
adequate teacher model in a number of queries that is polynomial in the size of
the minimal weighted automaton.. We include an algorithm for learning WAs over
any field based on a linear algebraic generalization of the Angluin-Schapire
algorithm. Together, this produces a surprising result: weighted automata over
fields are structured enough that even though they can be very compact, they
are still efficiently learnable.
