Аноним

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

Материал из WikiGrapp
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Проблема минимизации конечного автомата'''  
'''Проблема минимизации конечного автомата''' (''[[Problem of finite-state automaton minimization]]'')
(''[[Problem of finite-state automation minimization]]'') -
задача построения по любому [[конечный автомат|конечному автомату]] <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.


[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.