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

(''[[Problem of finite-state automation minimization]]'') -  

задача построения по любому [[конечный автомат|конечному автомату]] <math>M</math>

такого конечного автомата, допускающего язык <math>L(M)</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 \in \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> и одно из состояний

<math>q_3</math> или <math>q_4</math> не принадлежит <math>F</math>.

Состояния <math>q_1</math> и <math>q_2</math> ''неразличимы'',

если не существует такой цепочки <math>x \in \Sigma^*</math>, которая их