Мінімальний автомат
Автома́т мініма́льний — автомат, який в класі всіх автоматів, які реалізують заданий автоматний оператор, має найменшу можливу кількість станів.
Існують алгоритми знаходження мінімального автомата еквівалентного даному для детермінованих автоматів. Алгоритму знаходження мінімального автомата еквівалентного даному за поліноміальний час, якщо він недетермінований не існує, якщо тільки не виконується рівність класів P і NP.[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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.