Проблема минимизации конечного автомата: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Проблема минимизации конечного автомата''' (''Problem of finite-state automation minimization'') -...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Проблема минимизации конечного автомата''' | '''Проблема минимизации конечного автомата''' | ||
(''Problem of finite-state automation minimization'') - | (''[[Problem of finite-state automation minimization]]'') - | ||
задача построения по любому конечному | задача построения по любому [[конечный автомат|конечному автомату]] <math>M</math> | ||
автомату < | |||
(здесь и ниже конечным автоматом называется полностью определенный | (здесь и ниже конечным автоматом называется полностью определенный | ||
детерминированный конечный автомат) | детерминированный конечный автомат) | ||
такого конечного автомата, допускающего язык < | такого конечного автомата, допускающего язык <math>L(M)</math>, | ||
который имеет наименьшее число состояний среди всех таких конечных | который имеет наименьшее число состояний среди всех таких конечных | ||
автоматов. | автоматов. | ||
| Строка 13: | Строка 12: | ||
неразличимых состояний в исходном конечном автомате. | неразличимых состояний в исходном конечном автомате. | ||
Состояние < | Состояние <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) | ||
\Sigma^*<math> различает состояния < | \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_1</math> и <math>q_2</math> ''неразличимы'', | ||
Состояния < | если не существует такой цепочки <math>x \in \Sigma^*</math>, которая их | ||
если не существует такой цепочки < | |||
различает. | различает. | ||
==Литература== | ==Литература== | ||
Версия от 19:18, 24 декабря 2009
Проблема минимизации конечного автомата (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]