2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Thomas Andrews Jul 28 '14 at 3:53
  • $\begingroup$ 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"? $\endgroup$ – tom Jul 28 '14 at 6:01
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Awesome, this is it--thanks! $\endgroup$ – tom Jul 28 '14 at 20:30
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – tom Jul 28 '14 at 3:18
  • $\begingroup$ Actually I'll edit the original question, since I'm not confident this is right $\endgroup$ – tom Jul 28 '14 at 3:19
  • 2
    $\begingroup$ 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... $\endgroup$ – Thomas Andrews Jul 28 '14 at 3:21
  • $\begingroup$ Ah I see, that makes sense. Does the stuff I added to the question sound right? $\endgroup$ – tom Jul 28 '14 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.