Вообщем-то на Electronixe дали ответ. Продублирую его здесь.
Идея в том, что сначала надо определиться, что надо проверить, именно сам FSM или функциональность FSM в составе системы. Если вам надо проверить сам FSM, тогда значит собираете второй "эталонный" FSM и каждый шаг сравниваете их друг с другом. А если функциональность, ну например FSM модуля UART, то собираете тест, который шлет байтики туда и обратно, с разными уровнями ошибок и проверяете что все работает.
"эталонный" FSM должен быть, написан в другом стиле, языке, виде (таблично например). Как вариант есть RTL FSM и behaviour FSM.
Ну и классика: тестер и разработчик должны быть разными людьми.