4625
правок
Проблема минимизации конечного автомата: различия между версиями
Перейти к навигации
Перейти к поиску
Проблема минимизации конечного автомата (посмотреть исходный код)
Версия от 12:33, 5 июля 2011
, 5 июля 2011нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Проблема минимизации конечного автомата''' | '''Проблема минимизации конечного автомата''' (''[[Problem of finite-state automaton minimization]]'') — | ||
(''[[Problem of finite-state | задача построения по любому [[конечный автомат|конечному автомату]] <math>\,M</math> | ||
задача построения по любому [[конечный автомат|конечному автомату]] <math>M</math> | |||
(здесь и ниже конечным автоматом называется полностью определенный | (здесь и ниже конечным автоматом называется полностью определенный | ||
детерминированный конечный автомат) | детерминированный конечный автомат) | ||
такого конечного автомата, допускающего язык <math>L(M)</math>, | такого конечного автомата, допускающего язык <math>\,L(M)</math>, | ||
который имеет наименьшее число состояний среди всех таких конечных | который имеет наименьшее число состояний среди всех таких конечных | ||
автоматов. | автоматов. | ||
| Строка 12: | Строка 11: | ||
неразличимых состояний в исходном конечном автомате. | неразличимых состояний в исходном конечном автомате. | ||
Состояние <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 \Sigma^*</math> различает состояния <math>q_1</math> и <math>q_2</math> из <math>Q</math>, если <math>(q_1,x) | Говорят, что цепочка <math>x \in \Sigma^*</math> различает состояния <math>\,q_1</math> и <math>\,q_2</math> из <math>\,Q</math>, если <math>\,(q_1,x)\vdash^*(q_3,e)</math>, <math>(q_2,x) \vdash^*(q_4,e)</math> и одно из состояний <math>\,q_3</math> или <math>\,q_4</math> не принадлежит <math>\,F</math>. | ||
\vdash^*(q_3,e),(q_2,x) \vdash^*(q_4,e)</math> и одно из состояний | Состояния <math>\,q_1</math> и <math>\,q_2</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>, которая их | если не существует такой цепочки <math>x \in \Sigma^*</math>, которая их | ||
различает. | различает. | ||
==Литература== | ==Литература== | ||
* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||