1
$\begingroup$

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?

  • 1
    Please explain your notation: what does $Z_4$ mean?2011-12-04
  • 0
    I'm looking through the book right now, but, from other sources, I'm assuming its $Z \pmod{4}$2011-12-04
  • 0
    Yup, its $Z \pmod{4}$2011-12-04
  • 0
    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$.2011-12-04
  • 0
    Yes, I'm familiar with modular arithmetic, and it is mod 4.2011-12-04
  • 1
    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.2011-12-04

1 Answers 1

3

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?

  • 0
    yeah, I got it. Thanks a lot!2011-12-04
  • 0
    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?2011-12-04
  • 0
    @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?2011-12-04
  • 0
    Yeah, I guess that's what I'm asking.2011-12-04
  • 0
    @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.2011-12-04
  • 0
    @Dhaivat: Someone with a better knowledge of algebraic automata theory than I might be able to fit an understandable answer into a comment, but I don’t think that I can manage it; I’m much more familiar with automata in connection with formal languages (and no expert there, either). **Very** roughly, one consequence is something like this. There are several semigroups naturally associated with an automaton. One of them has the nice property that there is a map from the input alphabet to the semigroup that completely characterizes the automaton, in the sense that the automaton can be ...2011-12-04
  • 0
    @Dhaivat: ... recovered from the map. If the input alphabet is equipped with a semigroup operation, the automaton is a semigroup automaton iff this map is a semigroup homomorphism.2011-12-04
  • 0
    I see. Thanks a lot :)2011-12-04