Drawing a simple non-deterministic finite automaton (NFA)

Question

How can I draw NFA (automaton) for this question?

First it should accept:

• alphabet = x,y,z

• L= { w | w such that, one of the number of occurrence x,y,z is multiple of three. }

For example: {xxx, yyy, zzz, xyxyzzz, xyxyx, zyzyz...}

Answer 1

First let's start with the simpler question:
How would you draw this automaton for L' = {aⁿ | n % 3 == 0}?

You'd draw an automaton with 3 states - one for each possible modolus, and iterate between them for each appearance of a. The accepting state will be the one denoted for 0.

Now, after establishing that - for your problem, you need to have 3³ states for your automaton - all possible tuples for (x,y,z) where x,y,z are in {0,1,2}.

Your goal now is to understand What will your lamda be? Since it is your homework, I won't give the complete answer, only a hint:

If you see x and you are in state (a,b,c) - you want to advance to (a+1 %3 ,b,c)

Also think - what are the accepting states? hint: what was the accepting state for the simplified L'?

attachment: automaton for L' as described above.