"The regular languages over $A$ are the homomorphic pre-images in $A^*$ of subsets of finite monoids."

Question

I'm trying to understand the statement:

The regular languages over $A$ are the homomorphic pre-images in $A^∗$ of subsets of finite monoids.

which appears in the Wikipedia article on free monoids: http://en.wikipedia.org/wiki/Free_monoid. ($A^*$ is the free monoid over $A$.)

Can anyone explain what the statement means? I gather there's a homomorphism from A* to the set of subsets of some finite monoid (?). But what is the finite monoid, and what is the homomorphism?

I'd like to understand if this is actually a deep statement about regular languages or not :)

---

Edit: Let me write here what I gather from Thomas Andrews' answer. We let $A$ be some alphabet and let $A^*$ be the free monoid over $A$. So $A^*$ is just the strings made of letters from $A$.

We think of each element of monoid $M$ as being some state of a finite state machine. So if $a$ and $b$ are some strings in $A^*$, then $\phi(a)$ and $\phi(b)$ are some states in the FSM. (They are the states you would get to if you started on the start state and entered $a$ or $b$.)

$\phi$ then makes sense as a homomorphism: $\phi(a + b) = \phi(a) \star \phi(b)$ means "the state the string $a + b$ gets you to in the FSM is the same as first running string $a$ and then string $b$."

I don't think the monoid operation in $M$ (i.e. $\star$) makes sense though...

Answer 1

Here is the missing part in Thomas' answer.

Let $\mathcal{A} = (Q, A, \cdot, q_0, F)$ be a complete deterministic automaton. Then each word $u$ defines a transformation $q \to q\cdot u$ on $Q$, which maps each state $q$ onto the end state of the unique path with label $u$ and origin $q_0$.

One can also define $q\cdot u$ by induction on the length of $u$. First, the empty word defines the identity transformation: for each state $q$, $q \cdot 1 = q$. Next, for every word $u \in A^+$ and for every letter $a \in A$, one sets $q\cdot (ua) = (q\cdot u)\cdot a$. Note in particular that for all words $u, v \in A^*$, $(q\cdot u)\cdot v = q\cdot uv$.

Therefore, the function which maps a word $u$ onto the transformation $q \to q \cdot u$ defines an homomorphism $\mu$ from $A^*$ into the monoid of partial transformations on $Q$ under composition of transformations. The range of this map is a monoid $M(\mathcal{A})$, called the transformation monoid of $\mathcal{A}$.

Observe now that a word $u$ is accepted by $\mathcal{A}$ if and only if $q_0 \cdot u \in F$. It follows that $L = \mu^{-1}(P)$ where $ P = \{ m \in M(\mathcal{A}) \mid q_0 \cdot m \in F \} $.

Interestingly, a similar proof is possible if one starts from a NFA, but in this case, one needs to work with the monoid of all relations on $Q$. By the way, this gives as a corollary the equivalence between DFAs and NFAs.

Answer 2

I only have the obvious part so far.

Any homomorphism $\phi(a):A^*\to (M,*)$ where $M$ is a finite monoid and $F\subseteq M$ is a subset yields a finite state machine where each element of $M$ is a state, and the state reached from state $m$ with $a$ as the next letter is $m*\phi(a)$. Then $F$ just corresponds to the finite states.

I'm stuck on the other way around is a little harder. I thought I had an answer for that, but it got messed up.