Изменения
→Проверка через BFS
=== Проверка через BFS ===
Алгоритм заключается в синхронном обходе автоматов в ширину, проверяя, что по пути сохраняются терминальные состояния.
Псевдокод:
bfs()
queue.push( <0, 0> );
used1[0] = used2[0] = true;
while( !q.isEmpty() )
u = q.front.first;
v = q.front.second;
q.pop();
if(isTerminal1[u] != isTerminal2[v])
return false;
for(i = a..z)
if(!used1[automata1[u][i]] || !used2[automata2[v][i]])
q.push(make_pair(automata1[u][i], automata2[v][i]));
used1[automata1[u][i]] = used2[automata2[v][i]] = true;
return true;
