Изменения

Перейти к: навигация, поиск
Построение эквивалентного ДКА по НКА
# <tex>T_d = \{q \in Q_d | \exists p \in T : p \in q\}</tex>.
# <tex>\delta_d(q, c) = \cup_{i=1}^{m} \delta(a_i, c)</tex> при условии, что <tex>q = \{a_1, ..., a_m\}</tex>.
 
=== Алгоритм ===
'''Задание состояний:'''
 
&nbsp;&nbsp;&nbsp;&nbsp;Состояние нашего ДКА будет соответствовать подмножеству состояний НКА - то есть их будет ровно <tex>2^n</tex>.
 
'''Задание переходов:'''
 
&nbsp;&nbsp;&nbsp;&nbsp;Возьмём состояние нашего ДКА <tex>q</tex>, соответствующее подмножеству состояний НКА {{---}} <tex>(a_1, a_2, ..., a_m)</tex>, и символ <tex>c</tex>. Тогда <tex>\delta_D(q, c) = p</tex>, где p - состояние ДКА, соответствующее подмножеству состояний НКА - <tex>\cup_{i=1}^{m} \delta(a_i, c)</tex>, где <tex>\delta_D</tex> {{---}} функция перехода в ДКА, а <tex>\delta</tex> {{---}} функция перехода в НКА.
 
'''Задание стартового состояния:'''
 
&nbsp;&nbsp;&nbsp;&nbsp;Стартовое состояние - состояние ДКА, соответствующее множеству из одного стартового состояния НКА.
 
'''Задание терминальных вершин:'''
 
&nbsp;&nbsp;&nbsp;&nbsp;Если в подмножестве состояний НКА есть хотя бы одна терминальная вершина, то вершина ДКА, соответствующая этому подмножеству, будет терминальной.
 
'''Терминология:'''
 
&nbsp;&nbsp;&nbsp;&nbsp;<tex>q</tex> - состояние НКА.
 
&nbsp;&nbsp;&nbsp;&nbsp;<tex>q_d</tex> - состояние ДКА.
 
&nbsp;&nbsp;&nbsp;&nbsp;<tex>\delta</tex> - функция перехода в НКА.
 
&nbsp;&nbsp;&nbsp;&nbsp;<tex>\delta_D</tex> - функция перехода в ДКА.
 
&nbsp;&nbsp;&nbsp;&nbsp;<tex>q \in q_d</tex> - <tex>q</tex> принадлежит <tex>q_d</tex>, если множество состояний НКА, соответствующее состоянию <tex>q_d</tex>, содержит состояние <tex>q</tex>.
===Доказательство эквивалентности===
Анонимный участник

Навигация