Мінімальний автомат

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 05:14, 8 червня 2021, створена Olexa Riznyk (обговорення | внесок) (Скасовано останнє редагування (Abbyytt) і відновлено версію 28398831 Yuriz: не є значущим у контексті предмету статті)
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)
Перейти до навігації Перейти до пошуку

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

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

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

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

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

  • Енциклопедія кібернетики, т. 1, с. 23.
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (вид. 2). Addison–Wesley.
Отримано з https://uk.wikipedia.org/w/index.php?title=Мінімальний_автомат&oldid=32565419