Equivalence Problem: Example
Question:
L
(
M
1
)
=
L
(
M
2
)
?
a
f
s
q
b
a
a
b
M
1
:
a
q
b
a
a
p
s
b
b
M
2
:
A minimum state FA
b
a
b
b
{
f
}
a
{
s
,
q
}
M
min
1
:
a
b
b
{
p
,
q
}
a
{
s
}
M
min
2
:
Answer:
YES
because
M
min
1
coincides with
M
min
2
26/26