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!

2
Contributors
3
Replies
6
Views
5 Years
Discussion Span
Last Post by 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;
``````

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

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}
}
``````
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.