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

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...

• What do you men "I don't think the monoid operation in $M$ makes sense, though." You haven't defined it - it could be any (finite) monoid. The fact that $\phi(a+b)=\phi(a)\star\phi(b)$ is assumed, because we assumed $\phi$ was a homomorphism. The key is to define what the states are for the state machine, and the transitions - that is, when in state $s$, and given a letter $a\in A$, what does the machine transition to? That would be $m\star \phi(a)$. – Thomas Andrews Jul 28 '14 at 3:53
• What I meant was, there isn't an obvious monoid operation for a given finite state machine. But I re-read your answer and I agree that if we start with a monoid $M$, and define the machine as you described, then we get a finite state machine. I guess the part that's still unclear is whether all state machines (and hence all regular languages) can be obtained this way. I guess that's what you meant by "the other way around"? – tom Jul 28 '14 at 6:01

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 if 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.

• Awesome, this is it--thanks! – tom Jul 28 '14 at 20:30

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.

• Hmm, what is the significance of $F$ in your answer? M is finite too. Also, what do you mean by $(M, \star)$? Is $\star$ just the binary operation of the monoid? This was a very helpful answer though, it gave me an intuition I'll try to explain in a separate answer... – tom Jul 28 '14 at 3:18
• Actually I'll edit the original question, since I'm not confident this is right – tom Jul 28 '14 at 3:19
• You need to know which states are "accept" states to determine whether a words matches a finite state machine. The elements $F$ are the "accept" states. Basically, $\phi^{-1}(F)=L$ is the regular expression. Not "pre-image of subsets of finite monoids." $F$ is the subset... – Thomas Andrews Jul 28 '14 at 3:21
• Ah I see, that makes sense. Does the stuff I added to the question sound right? – tom Jul 28 '14 at 3:38