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