automatafinite-automata

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


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

with the following criteria:

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


Solution

  • 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":

    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:

    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:

    Demonstrate of NFA