Finite Automata Comparison

[noahjer]

Im trying to implement a program that will check the descriptions of two FA and check if they are equivalent.

Im assuming (for simplicity) that each FA is in minimal form, the input alphabet is {a b} and each FA only has one finish state.

Format for an FA is as follows: Number_States, Start_State, Finish_State, State_Number, Next_A, Next_B. So and example of it would be something like this, where the Start_State is 0 and the Finish_State is 4:

State   next_a      next_b
    0       0           1
    1       2           1
    2       0           3
    3       4           1
    4       4           4

Im also assuming that two FA are the equivalent if they have the same number of states and they are the same apart from state renumbering.

Right now, I can eeasily check if two FA are the same by looping throughout the 2d arrays and checking if each number is the exact same. However, I'm not sure exactly how to be able to see if they are equivalent if the states are renumbered.

For example, these two arrays are the exact same, so it returns true.

int fa_1[5][2] = {{0, 1},
                  {2, 1},
                  {0, 3},
                  {4, 1},
                  {4, 4}};

int fa_2[5][2] = {{0, 1},
                  {2, 1},
                  {0, 3},
                  {4, 1},
                  {4, 4}};

For example, these two arrays are not equivalent, it has a 2 instead of a 0 in the third row and thus doesn't define the same language.

int fa_1[5][2] = {{0, 1},
                  {2, 1},
                  {0, 3},
                  {4, 1},
                  {4, 4}};

int fa_2[5][2] = {{0, 1},
                  {2, 1},
                  {2, 3},
                  {4, 1},
                  {4, 4}};

For example, these two arrays don't have the same exact numbers, but they are equivalent because they define the same language.

int fa_1[5][2] = {{0, 1},
                  {2, 1},
                  {0, 3},
                  {4, 1},
                  {4, 4}};

int fa_2[5][2] = {{1, 2},
                  {3, 2},
                  {1, 4},
                  {5, 2},
                  {5, 5}};

Sorry if I explained it confusingly, I'm just not sure how to see if they are equivalent based on the renumbering part....

Any help is appreciated!

[deceptikon]

I'm just not sure how to see if they are equivalent based on the renumbering part....

If one number is shifted by a certain amount, all numbers will be shifted by the same amount. So when comparing the two arrays you can determine the shift amount by the very first number in both arrays and then apply it to all other numbers as you compare them:

// Compare x with a shift toward y
if (x[i] + shift != y[i])
    return false;

[noahjer]

Thanks for the response. I thought of that as well but not all numbers necessarily have to be shifted by the same amount. Its the path of the numbers that is taken into account.

For instance,

FA_1
   state   next_a      next_b
    0       0           1
    1       2           1
    2       0           3
    3       4           1
    4       4           4

FA_2
   state   next_a      next_b
    23       23           34
    34       62           34
    62       23           72
    72       88           34
    88       88           88

int fa_1[5][2] = {{0, 1},
                  {2, 1},
                  {0, 3},
                  {4, 1},
                  {4, 4}};

int fa_2[5][2] = {{23, 34},
                  {62, 34},
                  {23, 72},
                  {88, 34},
                  {88, 88}};

Would yield an equivalent FA because they both define the same language

[deceptikon]

I thought of that as well but not all numbers necessarily have to be shifted by the same amount.

Okay, so you're looking for a pattern where the marker for a point in the pattern (ie. the FA language) isn't fixed. That's not a great deal harder if we're assuming that the overall pattern is constant and only the names/values of each node will vary, you can convert the variable language into a fixed language and then compare. So the original numbers would go away and be replaced with a normalized description:

{
    {A, B}
    {C, B}
    {A, D}
    {E, B}
    {E, E}
}