Эквивалентность состояний ДКА — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Проверка эквивалентности автоматов)
(Эквивалентность автоматов)
Строка 4: Строка 4:
 
<font face="Times" size="3">
 
<font face="Times" size="3">
  
*'''Определение: ''' Два <em> автомата</em> <tex>\mathcal{A}_1(Q_1,\Sigma,\delta_1,s_10, T_1\subseteq Q_1)</tex> и <tex>\mathcal{A}_2(Q_2,\Sigma,\delta_2,s_20, T_2\subseteq Q_2)</tex> называются <em>эквивалентными</em>, если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>.
+
*'''Определение: ''' Два <em> автомата</em> <tex>\mathcal{A}_1(Q_1,\Sigma,\delta_1,s_{10}, T_1\subseteq Q_1)</tex> и <tex>\mathcal{A}_2(Q_2,\Sigma,\delta_2,s_{20}, T_2\subseteq Q_2)</tex> называются <em>эквивалентными</em>, если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>.
 
*'''Определение: ''' Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются <em>эквивалентными</em> <tex>(q_i \sim q_j)</tex>, если <tex>\forall z\in \Sigma^*</tex>  верно, что <tex>\delta(q_i, z)\in T \Leftrightarrow \delta(q_j, z)\in T</tex>. Из этого следует, что если два состояния <tex>q_i</tex> и <tex>q_j</tex> эквивалентны, то и состояния <tex>\delta_1(q_i, a)</tex> и <tex>\delta_2(q_j, a)</tex> будут эквивалентными для <tex>\forall a \in \Sigma</tex>. Кроме того, т.к. переход <tex>\delta(q, \varepsilon)</tex> может возникнуть только для конечного состояния <tex>q</tex>, то никакое допускающее(терминальное) состояние не может быть эквивалентно не допускающему состоянию. Нахождение классов эквивалентных состояний внутри автомата и их совмещение в одно состояние используется в быстром алгоритме Хопкрофта для минимизации автомата, работающий за <tex>O(n \log n)</tex>.
 
*'''Определение: ''' Два <em> состояния</em> <tex>q_i</tex> и <tex>q_j</tex> называются <em>эквивалентными</em> <tex>(q_i \sim q_j)</tex>, если <tex>\forall z\in \Sigma^*</tex>  верно, что <tex>\delta(q_i, z)\in T \Leftrightarrow \delta(q_j, z)\in T</tex>. Из этого следует, что если два состояния <tex>q_i</tex> и <tex>q_j</tex> эквивалентны, то и состояния <tex>\delta_1(q_i, a)</tex> и <tex>\delta_2(q_j, a)</tex> будут эквивалентными для <tex>\forall a \in \Sigma</tex>. Кроме того, т.к. переход <tex>\delta(q, \varepsilon)</tex> может возникнуть только для конечного состояния <tex>q</tex>, то никакое допускающее(терминальное) состояние не может быть эквивалентно не допускающему состоянию. Нахождение классов эквивалентных состояний внутри автомата и их совмещение в одно состояние используется в быстром алгоритме Хопкрофта для минимизации автомата, работающий за <tex>O(n \log n)</tex>.
 
*'''Определение:''' Слово <tex>z \in \Sigma^*</tex> различает два состояния <tex>(q_i \nsim q_j)</tex>, если <tex>\delta(q_i, z)\in T \Leftrightarrow \delta(q_j, z)\notin T</tex>. Также, если слово <tex>z</tex> различает состояния <tex>t_1</tex> и <tex>t_2</tex> такие, что <tex>t_1=\delta(q_1, a)</tex> и <tex>t_2=\delta(q_2, a)</tex>, то слово <tex>aw</tex> различает состояния <tex>q_1</tex> и <tex>q_2</tex>. Нахождение пар различных состояний в автомате используется в алгоритме минимизации автомата, работающий за <tex>O(n^2)</tex>.  
 
*'''Определение:''' Слово <tex>z \in \Sigma^*</tex> различает два состояния <tex>(q_i \nsim q_j)</tex>, если <tex>\delta(q_i, z)\in T \Leftrightarrow \delta(q_j, z)\notin T</tex>. Также, если слово <tex>z</tex> различает состояния <tex>t_1</tex> и <tex>t_2</tex> такие, что <tex>t_1=\delta(q_1, a)</tex> и <tex>t_2=\delta(q_2, a)</tex>, то слово <tex>aw</tex> различает состояния <tex>q_1</tex> и <tex>q_2</tex>. Нахождение пар различных состояний в автомате используется в алгоритме минимизации автомата, работающий за <tex>O(n^2)</tex>.  
Строка 14: Строка 14:
  
 
</font>
 
</font>
 +
 
== Проверка эквивалентности автоматов ==
 
== Проверка эквивалентности автоматов ==
  

Версия 05:24, 10 октября 2010

Эквивалентность автоматов

  • Определение: Два автомата [math]\mathcal{A}_1(Q_1,\Sigma,\delta_1,s_{10}, T_1\subseteq Q_1)[/math] и [math]\mathcal{A}_2(Q_2,\Sigma,\delta_2,s_{20}, T_2\subseteq Q_2)[/math] называются эквивалентными, если они распознают один и тот же язык над алфавитом [math]\Sigma[/math].
  • Определение: Два состояния [math]q_i[/math] и [math]q_j[/math] называются эквивалентными [math](q_i \sim q_j)[/math], если [math]\forall z\in \Sigma^*[/math] верно, что [math]\delta(q_i, z)\in T \Leftrightarrow \delta(q_j, z)\in T[/math]. Из этого следует, что если два состояния [math]q_i[/math] и [math]q_j[/math] эквивалентны, то и состояния [math]\delta_1(q_i, a)[/math] и [math]\delta_2(q_j, a)[/math] будут эквивалентными для [math]\forall a \in \Sigma[/math]. Кроме того, т.к. переход [math]\delta(q, \varepsilon)[/math] может возникнуть только для конечного состояния [math]q[/math], то никакое допускающее(терминальное) состояние не может быть эквивалентно не допускающему состоянию. Нахождение классов эквивалентных состояний внутри автомата и их совмещение в одно состояние используется в быстром алгоритме Хопкрофта для минимизации автомата, работающий за [math]O(n \log n)[/math].
  • Определение: Слово [math]z \in \Sigma^*[/math] различает два состояния [math](q_i \nsim q_j)[/math], если [math]\delta(q_i, z)\in T \Leftrightarrow \delta(q_j, z)\notin T[/math]. Также, если слово [math]z[/math] различает состояния [math]t_1[/math] и [math]t_2[/math] такие, что [math]t_1=\delta(q_1, a)[/math] и [math]t_2=\delta(q_2, a)[/math], то слово [math]aw[/math] различает состояния [math]q_1[/math] и [math]q_2[/math]. Нахождение пар различных состояний в автомате используется в алгоритме минимизации автомата, работающий за [math]O(n^2)[/math].
  • Пример двух эквивалентных автоматов:

Automata1.pngAutomata2.png

Состояния [math]B[/math] и [math]C[/math] допускающие.

Проверка эквивалентности автоматов

  • Если положить, что начальные состояния эквивалентны, то последовательно, переходя по одному символу из состояний, можем получить и другие пары эквивалентных состояний. Если же в одну из таких пар попадут допускающее состояния вместе с не допускающим, то такие [math]q_i[/math] и [math]q_j[/math] неэквивалентны.CheckEquival.png
  • Таким образом получим разбиение множества [math] Q_1\cup Q_2[/math] на множества эквивалентных состояний. После этого проверим, что никакое из этих множеств не содержит допускающее и не допускающее состояние одновременно, тогда автоматы эквивалентны.

Литература

  • Н.Н. Вояковская, А.Е. Москаль, Д.Ю. Булычев, А.А. Терехов - "Разработка компиляторов"