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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность автоматов)
(Эквивалентность автоматов)
Строка 8: Строка 8:
 
*'''Определение:''' Слово <tex>z \in \Sigma^*</tex> различает два состояния <tex>(s_i \nsim s_j)</tex>, если <tex>\delta(s_i, z)\in T \Leftrightarrow \delta(s_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>(s_i \nsim s_j)</tex>, если <tex>\delta(s_i, z)\in T \Leftrightarrow \delta(s_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>.  
  
'''Пример двух эквивалентных автоматов:'''
+
*'''Пример двух эквивалентных автоматов:'''
<math>\begin{array}{|c|c|c|}
+
    <math>
 +
\begin{array}{|c|c|c|}  
 +
\hline                 
 +
Q\diagdown \Sigma & a & b\\
 +
\hline\hline A & B & C\\
 +
\hline B & B & D\\
 +
\hline C & B & C\\
 +
\hline D & B & E\\
 +
\hline E & B & C\\
 +
\hline F & E & E\\
 
\hline
 
\hline
 +
\end{array}
 +
</math>      <tex>\sim</tex>      <math>
 +
\begin{array}{|c|c|c|} 
 +
\hline                 
 
Q\diagdown \Sigma & a & b\\
 
Q\diagdown \Sigma & a & b\\
\hline A & B & C\\
+
\hline\hline - & & \\
 
\hline B & B & D\\
 
\hline B & B & D\\
 
\hline C & B & C\\
 
\hline C & B & C\\
 
\hline D & B & E\\
 
\hline D & B & E\\
 
\hline E & B & C\\
 
\hline E & B & C\\
\hline F & E & E\\
+
\hline - & & \\
 
\hline
 
\hline
 
\end{array}
 
\end{array}
</math>
 
</font>
 

Версия 08:18, 1 октября 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]s_i[/math] и [math]s_j[/math] называются эквивалентными [math](s_i \sim s_j)[/math], если [math]\forall z\in \Sigma^*[/math] верно, что [math]\delta(s_i, z)\in T \Leftrightarrow \delta(s_j, z)\in T[/math]. Из этого следует, что если два состояния [math]s_i[/math] и [math]s_j[/math] эквивалентны, то и состояния [math]\delta_1(s_i, a)[/math] и [math]\delta_2(s_j, a)[/math] будут эквивалентными для [math]\forall a \in \Sigma[/math]. Кроме того, т.к. переход [math]\delta(s, \varepsilon)[/math] может возникнуть только для конечного состояния [math]s[/math], то никакое допускающее(терминальное) состояние не может быть эквивалентно не допускающему состоянию. Нахождение классов эквивалентных состояний внутри автомата и их совмещение в одно состояние используется в быстром алгоритме Хопкрофта для минимизации автомата, работающий за [math]O(n \log n)[/math].
  • Определение: Слово [math]z \in \Sigma^*[/math] различает два состояния [math](s_i \nsim s_j)[/math], если [math]\delta(s_i, z)\in T \Leftrightarrow \delta(s_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].
  • Пример двух эквивалентных автоматов:
   [math]
\begin{array}{|c|c|c|}   
\hline                   
Q\diagdown \Sigma & a & b\\
\hline\hline A & B & C\\
\hline B & B & D\\
\hline C & B & C\\
\hline D & B & E\\
\hline E & B & C\\
\hline F & E & E\\
\hline
\end{array}
[/math]       [math]\sim[/math]      <math>

\begin{array}{|c|c|c|} \hline Q\diagdown \Sigma & a & b\\ \hline\hline - & & \\ \hline B & B & D\\ \hline C & B & C\\ \hline D & B & E\\ \hline E & B & C\\ \hline - & & \\ \hline \end{array}