# Finite Automata, basic question with semigroups

If we use the notation where when we say:

$$M = M(G)$$

We mean to say that $M$ is a automata with states and alphabet elements of $G$.

From here, I am posed this question (Abstract Algebra by Pinter):

Describe $M(Z_4)$, give the table of its next-state function as well as its state diagram.

I cannot understand how I am to do this, since

• I'm not given an operation (although I suspect it is assumed to be multiplication)
• If I do multiplication over $Z_4$, it gives me a infinite state diagram, which I do not quite understand.

Any help?

-
Please explain your notation: what does $Z_4$ mean? – Srivatsan Dec 4 '11 at 1:08
I'm looking through the book right now, but, from other sources, I'm assuming its $Z \pmod{4}$ – Dhaivat Pandya Dec 4 '11 at 1:10
Yup, its $Z \pmod{4}$ – Dhaivat Pandya Dec 4 '11 at 1:12
Since this is from computer science context, it is likely that it is integers modulo 4. Do you know about modular arithmetic (precisely speaking, about the ring/group $\mathbb Z / 4 \mathbb Z$)? Note: $\mathbb Z/4 \mathbb Z$ is the notation more commonly used by mathematicians to denote what you call $Z_4$. – Srivatsan Dec 4 '11 at 1:13
I suspect that in fact the intended operation is addition mod $4$, but addition and multiplication mod $4$ will both have only four states, one for each of the numbers $0,1,2,3$. The next-state function for either operation will have $16$ entries, one for each possible combination of present state and input. – Brian M. Scott Dec 4 '11 at 1:17

I’ll write $\nu(s,i)=t$ to mean that if the automaton is in state $s$, and the input is $i$, the next state is $t$. I’ll use $0,1,2$, and $3$ for the elements of the group. If the intended operation is multiplication mod $4$, you want $\nu(s,i)$ to be $s\cdot i$; if, as I suspect, it’s addition mod $4$, you want $\nu(s,i)$ to be $s+i$. Thus, for example, if it’s multiplication, you’ll have $\nu(s,0)=0$ and $\nu(s,1)=s$ for every $s$, while if it’s addition, you’ll have $\nu(s,0)=s$ for every $s$. Can you take it from there?

-
yeah, I got it. Thanks a lot! – Dhaivat Pandya Dec 4 '11 at 1:55
This doesn't really stop me from wondering, why does it help for $G$ to be a semigroup? Does that lead to any interesting properties of the automaton? – Dhaivat Pandya Dec 4 '11 at 1:56
@Dhaivat: In order to define an automaton in this way, you clearly need to have a set equipped with a binary operation. Are you asking whether requiring the operation to be associative does anything useful? – Brian M. Scott Dec 4 '11 at 2:01
Yeah, I guess that's what I'm asking. – Dhaivat Pandya Dec 4 '11 at 2:09
@Dhaivat: It does have some nice consequences, but they’re at a fairly abstract level. Very roughly, there are important connections between automata and semigroups in general, and within this body of theory semigroup automata behave especially nicely in certain respects. – Brian M. Scott Dec 4 '11 at 2:51