Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
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. –  Brian M. Scott Dec 4 '11 at 1:17
show 1 more comment

1 Answer

up vote 3 down vote accepted

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?

share|improve this answer
    
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
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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