Відмінності між версіями «Мінімальний автомат»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
 
Рядок 1: Рядок 1:
'''Автома́т мініма́льний''' — [[автомат]], який в класі всіх автоматів, які реалізують заданий [[оператор автоматний|автоматний оператор]], має найменшу можливу кількість станів.
+
'''Автома́т мініма́льний''' — [[автомат]], який в класі всіх автоматів, які реалізують заданий [[Скінченний автомат#Автоматні оператори|автоматний оператор]], має найменшу можливу кількість станів.
   
 
Існують [[Мінімізація ДСкА|алгоритми знаходження мінімального автомата еквівалентного даному для детермінованих автоматів]]. Алгоритму знаходження мінімального автомата еквівалентного даному за поліноміальний час, якщо він недетермінований не існує, якщо тільки не виконується [[рівність класів P і NP]].{{sfn|Hopcroft|Motwani|Ullman|2001|p=163}}
 
Існують [[Мінімізація ДСкА|алгоритми знаходження мінімального автомата еквівалентного даному для детермінованих автоматів]]. Алгоритму знаходження мінімального автомата еквівалентного даному за поліноміальний час, якщо він недетермінований не існує, якщо тільки не виконується [[рівність класів P і NP]].{{sfn|Hopcroft|Motwani|Ullman|2001|p=163}}

Поточна версія на 12:54, 27 травня 2020

Автома́т мініма́льний — автомат, який в класі всіх автоматів, які реалізують заданий автоматний оператор, має найменшу можливу кількість станів.

Існують алгоритми знаходження мінімального автомата еквівалентного даному для детермінованих автоматів. Алгоритму знаходження мінімального автомата еквівалентного даному за поліноміальний час, якщо він недетермінований не існує, якщо тільки не виконується рівність класів P і NP.[1]

Зноски[ред. | ред. код]

  1. Hopcroft, Motwani та Ullman, 2001, с. 163

Література[ред. | ред. код]