Find a finite automata that for the language L={0,1,2} | needs to include 1002 1,2 are odd and 0 is even

Question

Find a finite automata that for the language L={0,1,2}

with the following criteria:

• The word must contain "1002".
• The number of occurrences of 1 must be odd
• The number of occurrences of 2 must be odd
• The number of occurrences of 0 must be even

I was able to prove regularity but as soon as it came to drawing it on paper I tried multiple things but couldn't find a way to do it

Answer 1

Does finite automata mean that I can use NFA (instead of DFA) right? So because we need the string to contains "1002", so in the remaining string, we have "the number of occurrent of character always even":

• Even 0

• Even 1

• Even 2

However, because the three conditions above is separate, so we will use a 3-bit number to store the current state (is even). Called the state from q0 (000) to q7 (111). In the same order, the 1st leftmost bit is even 0, 2nd left most is even 1, and the same for character 2.

For example, the state:

• q1 = 001 means that the string contains odd 2, and not odd 0, not odd 1

• q7 = 111 means that the string contains odd 0, 1 & 2

Note that not even means can be 0

So the initial state will be q0, then we need to construct the path like:

q0 -> 0 -> q4 (100)

q0 -> 1 -> q2 (010)

q0 -> 2 -> q1 (001)

Then, in the same way, we can construct the path for, example q1:

q1 -> 0 -> q5 (101)

q1 -> 1 -> q3 (011)

q1 -> 2 -> q0 (000)

Lastly, the problem is it must contain "1002". To verify this, we create q8 (1), q9 (0), q10 (0), q11 (2).

The flow will be q8 -> q9 -> q10. However, after verify the "1002", we need to know the previous status (the odd/even of characters).

To do this, we will duplicated from q0 to q7 as q0' to q7'. Then, I called X is a group of q8->q9->q10. So each state from q0, to q7 will have a path like q3--1-->X--2-->q3'. This will keep the previous state but also do verify the "1002" string.

As a result, the acceptable state is q0'. You can refer to the below image: