Проблема минимизации конечного автомата

Проблема минимизации конечного автомата (Problem of finite-state automation minimization) - задача построения по любому конечному автомату </math>M[math]\displaystyle{ (здесь и ниже конечным автоматом называется полностью определенный детерминированный конечный автомат) такого конечного автомата, допускающего язык }[/math]L(M)[math]\displaystyle{ , который имеет наименьшее число состояний среди всех таких конечных автоматов. Имеет эффективное решение путем исключения недостижимых состояний и склеивания неразличимых состояний в исходном конечном автомате. Состояние }[/math]q \in Q[math]\displaystyle{ автомата }[/math]M=(Q, \Sigma,\delta, q_0,F)[math]\displaystyle{ называется ''недостижимым'', если не существует такой входной цепочки }[/math]x[math]\displaystyle{ , что }[/math](q_0,x) \vdash^*(q,e)[math]\displaystyle{ . Говорят, что цепочка }[/math]x \in \Sigma^*[math]\displaystyle{ различает состояния }[/math]q_1[math]\displaystyle{ и }[/math]q_2[math]\displaystyle{ из }[/math]Q[math]\displaystyle{ , если }[/math](q_1,x) \vdash^*(q_3,e),(q_2,x) \vdash^*(q_4,e)[math]\displaystyle{ и одно из состояний }[/math]q_3[math]\displaystyle{ или }[/math]q_4[math]\displaystyle{ не принадлежит }[/math]F[math]\displaystyle{ . Состояния }[/math]q_1[math]\displaystyle{ и }[/math]q_2[math]\displaystyle{ ''неразличимы'', если не существует такой цепочки }[/math]x \in \Sigma^*<math>, которая их различает.

Литература

[Ахо-Хопкрофт-Ульман],

[Касьянов/95]