Изменения

Перейти к: навигация, поиск

Детерминированные конечные автоматы

365 байт добавлено, 10 январь
Bug fixed by zhelenskiy
=== Псевдокод ===
* <tex> \mathtt {Transitions} </tex> {{---}} множество пар <tex>\langle a</tex>, <tex>T \rangle</tex> , где <tex> a \in \Sigma</tex>, <tex>T \in Q</tex>
* <tex> \mathtt {Assotiations} </tex> {{---}} массив, где каждому состоянию первого автомата соответствует найденное состояние второго автомата. Изначально заполнен -1.
'''boolean''' dfs(u: '''Vertex''', v: '''Vertex'''):
visited[u] = ''true'' <font color="green">// заметим, что достаточно только одного массива <tex>\mathtt{visited}</tex> на два автомата</font>
'''if''' (v.terminal '''!=''' u.terminal)
'''return''' ''false''
associations[u] = v
'''boolean''' result = ''true''
'''for''' (<tex>\langle c, q \rangle</tex> : u.transitions)
'''if''' одна из вершин t1, t2 ''дьявольская'', а другая {{---}} нет
'''return''' ''false''
'''if''' (visited[t1]) result = result '''and'not''t2 ' visited''==''' associations[t1]) '''else'''
result = result '''and''' dfs(t1, t2)
Анонимный участник

Навигация