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
    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
    I see. Thanks a lot :)2011-12-04