Изменения
Новая страница: «== Эквивалентность автоматов == <font face="Times" size="3"> *'''Определение: ''' Два <em> автомата</em> <tex>\mathca…»
== Эквивалентность автоматов ==
<font face="Times" size="3">
*'''Определение: ''' Два <em> автомата</em> <tex>\mathcal{A}_1(Q_1,\Sigma,\delta_1,s_10, T_1\subset Q_1)</tex> и <tex>\mathcal{A}_2(Q_2,\Sigma,\delta_2,s_20, T_2\subset Q_2)</tex> называются <em>эквивалентными</em>, если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>.
*'''Определение: ''' Два <em> состояния</em> <tex>s_i</tex> и <tex>s_j</tex> называются <em>эквивалентными</em> <tex>(s_i \sim s_j)</tex>, если <tex>\forall z\in \Sigma^*</tex> верно, что <tex>\delta(s_i, z)\in T \Leftrightarrow \delta(s_j, z)\in T</tex>. Из этого следует, что если два состояния <tex>s_i</tex> и <tex>s_j</tex> эквивалентны, то и состояния <tex>\delta_1(s_i, a)</tex> и <tex>\delta_2(s_j, a)</tex> будут эквивалентными для <tex>\forall a \in \Sigma</tex>. Кроме того, т.к. переход <tex>\delta(s, \varepsilon)</tex> может возникнуть только для конечного состояния <tex>s</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>. Нахождение пар различных состояний в автомате также используется для минимизации автомата.
</font>
<font face="Times" size="3">
*'''Определение: ''' Два <em> автомата</em> <tex>\mathcal{A}_1(Q_1,\Sigma,\delta_1,s_10, T_1\subset Q_1)</tex> и <tex>\mathcal{A}_2(Q_2,\Sigma,\delta_2,s_20, T_2\subset Q_2)</tex> называются <em>эквивалентными</em>, если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>.
*'''Определение: ''' Два <em> состояния</em> <tex>s_i</tex> и <tex>s_j</tex> называются <em>эквивалентными</em> <tex>(s_i \sim s_j)</tex>, если <tex>\forall z\in \Sigma^*</tex> верно, что <tex>\delta(s_i, z)\in T \Leftrightarrow \delta(s_j, z)\in T</tex>. Из этого следует, что если два состояния <tex>s_i</tex> и <tex>s_j</tex> эквивалентны, то и состояния <tex>\delta_1(s_i, a)</tex> и <tex>\delta_2(s_j, a)</tex> будут эквивалентными для <tex>\forall a \in \Sigma</tex>. Кроме того, т.к. переход <tex>\delta(s, \varepsilon)</tex> может возникнуть только для конечного состояния <tex>s</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>. Нахождение пар различных состояний в автомате также используется для минимизации автомата.
</font>
