Проблема минимизации конечного автомата: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Создана новая страница размером '''Проблема минимизации конечного автомата''' (''Problem of finite-state automation minimization'') -...)
 
Нет описания правки
Строка 1: Строка 1:
'''Проблема минимизации конечного автомата'''  
'''Проблема минимизации конечного автомата'''  
(''Problem of finite-state automation minimization'') -  
(''[[Problem of finite-state automation minimization]]'') -  
задача построения по любому конечному
задача построения по любому [[конечный автомат|конечному автомату]] <math>M</math>
автомату </math>M<math>
(здесь и ниже конечным автоматом называется полностью определенный
(здесь и ниже конечным автоматом называется полностью определенный
детерминированный конечный автомат)
детерминированный конечный автомат)
такого конечного автомата, допускающего язык </math>L(M)<math>,
такого конечного автомата, допускающего язык <math>L(M)</math>,
который имеет наименьшее число состояний среди всех таких конечных
который имеет наименьшее число состояний среди всех таких конечных
автоматов.
автоматов.
Строка 13: Строка 12:
неразличимых состояний в исходном конечном автомате.
неразличимых состояний в исходном конечном автомате.


Состояние </math>q \in Q<math> автомата </math>M=(Q, \Sigma,\delta, q_0,F)<math>
Состояние <math>q \in Q</math> автомата <math>M=(Q, \Sigma,\delta, q_0,F)</math>
называется ''недостижимым'', если не существует такой входной
называется ''недостижимым'', если не существует такой входной
цепочки </math>x<math>, что </math>(q_0,x) \vdash^*(q,e)<math>.
[[цепочка|цепочки]] <math>x</math>, что <math>(q_0,x) \vdash^*(q,e)</math>.
Говорят, что цепочка </math>x \in
Говорят, что цепочка <math>x \in \Sigma^*</math> различает состояния <math>q_1</math> и <math>q_2</math> из <math>Q</math>, если <math>(q_1,x)
\Sigma^*<math> различает состояния </math>q_1<math> и </math>q_2<math> из </math>Q<math>, если </math>(q_1,x)
\vdash^*(q_3,e),(q_2,x) \vdash^*(q_4,e)</math> и одно из состояний
\vdash^*(q_3,e),(q_2,x) \vdash^*(q_4,e)<math> и одно из состояний
<math>q_3</math> или <math>q_4</math> не принадлежит <math>F</math>.
</math>q_3<math> или </math>q_4<math> не принадлежит </math>F<math>.
Состояния <math>q_1</math> и <math>q_2</math> ''неразличимы'',
Состояния </math>q_1<math> и </math>q_2<math> ''неразличимы'',
если не существует такой цепочки <math>x \in \Sigma^*</math>, которая их
если не существует такой цепочки </math>x \in \Sigma^*<math>, которая их
различает.
различает.
==Литература==
==Литература==

Навигация