Изменения

Перейти к: навигация, поиск
Алгоритм
===Алгоритм===
* <tex>\mathtt{P}</tex> {{---}} очередь состояний, соответствующих множествам, состоящих из состояний НКА.
* <tex>\mathtt{QQ_d}</tex> {{---}} массив множеств, соответствующих состояниям ДКА.
* <tex>\mathtt{s}</tex> {{---}} стартовое состояние НКА.
'''Automaton''' getDFAbyNFA(<tex>\langle \Sigma, Q_0Q, s, T_0T, \delta_0 delta \rangle</tex> : '''Automaton'''):
<tex>P</tex>.push({s})
<tex>QQ_d</tex> = <tex>\varnothing</tex>
'''while''' <tex>P</tex> <tex> \neq </tex> <tex>\varnothing </tex>
<tex>P</tex>.pop(<tex>p_d</tex>)
<tex>q_d</tex> = <tex>\varnothing</tex>
'''for''' <tex>p \in p_d</tex>
<tex>q_d</tex> = <tex>q_d \cup \{ \delta_0delta(p, c) \}</tex> <tex>\deltadelta_d(p_d, q_d)</tex> = <tex>c</tex> '''if''' <tex>q_d \notin QQ_d</tex>
<tex>P</tex>.push(<tex>q_d</tex>)
<tex>QQ_d</tex>.add(<tex>q_d</tex>) <tex>TT_d</tex> = <tex>\{q \in Q Q_d \mid \exists p \in T : p \in q\}</tex> '''return''' <tex>\langle \Sigma, QQ_d, \{s\}, TT_d, \delta delta_d \rangle</tex>
===Асимптотика===
Анонимный участник

Навигация