Algorithm: Equivalence Problem
•
Input:
Two minimum state FA
,
M
1
and
M
2
•
Output:
YES
if
L
(
M
1
)
=
L
(
M
2
)
NO
if
L
(
M
1
)
¹
L
(
M
2
)
•
Method:
•
if
M
1
coincides with
M
2
except for the name of states
then
write (’
YES
’)
else
write (’
NO
’)
The equivalence problem for FA is decidable
Summary:
25/26