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

Проблема минимизации конечного автомата (Problem of finite-state automation minimization) - задача построения по любому конечному автомату [math]\displaystyle{ M }[/math] (здесь и ниже конечным автоматом называется полностью определенный детерминированный конечный автомат) такого конечного автомата, допускающего язык [math]\displaystyle{ L(M) }[/math], который имеет наименьшее число состояний среди всех таких конечных автоматов.

Имеет эффективное решение путем исключения недостижимых состояний и склеивания неразличимых состояний в исходном конечном автомате.

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

Литература

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

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