Изменения

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

Алгоритм Бржозовского

625 байт добавлено, 18:34, 16 октября 2016
Нет описания правки
{{Определение
|definition=
'''Обратный язык''' для языка <tex>L</tex> {{---}} язык <tex>r(L) = \{ u \mid r(u) \in L \}</tex>.
}}
Если левый язык состояния <tex>q</tex> в <tex>\mathcal{A}</tex> {{---}} <tex>L_g(q)</tex>, тогда его левый язык в <tex>r(A)</tex> {{---}} <tex>L_d(q)</tex>. Аналогично для правого языка <tex>q</tex>.
}}
 
Пусть <tex>\mathcal{A} = \langle \Sigma , Q , I , T , \delta \rangle</tex> {{---}} [[Недетерминированные_конечные_автоматы|НКА]].<br>Тогда детерминированный автомат <tex>d(\mathcal{A}) = \langle \Sigma , Q' , \{ i' \} , T' , \delta' \rangle</tex> определяется следующим образом:
* Детерминированному состоянию соответствует множество недетерминированных состояний: для каждого <tex>q' \in Q'</tex> имеем <tex>q' \subseteq Q</tex>,
==Алгоритм==
188
правок

Навигация