Минимизация дискретного конечного автомата — это стандартная задача в информатике. Каковы преимущества минимизации конечных автоматов? Это просто академическая проблема?
В чем преимущество минимизации конечных автоматов?
comment
Связанный: stackoverflow .com/questions/1514736/
- person Doc Brown schedule 18.05.2013
Ответы (2)
Основной причиной минимизации конечного автомата является снижение стоимости реализации. При изучении конечных автоматов речь шла о машинах, реализующих изучаемую функцию. Когда инвертор, затвор или компонент памяти состояли из одной или нескольких электронных ламп, http://en.wikipedia.org/wiki/Vacuum_tube — устройства, которые стоили денег, потребляли энергию и занимали немало места, очень-очень хотелось уменьшить количество трубок и соединений между ними.
Даже с переходом на твердотельные реализации недвижимость часто вызывала беспокойство. Если конкретный конечный автомат часто повторно использовался в системе, оптимизация FA приносила большие дивиденды в виде выхода чипов.
person
Bob Dalgleish
schedule
18.05.2013
Вы, кажется, предполагаете, что минимальные FA представляют только исторический интерес. Это чепуха. В НЛП и компиляторах FA все еще широко распространены, а не минимизированные FA могут стать слишком большими для эффективного хранения/обработки.
- person Fred Foo; 18.05.2013
Я согласен с тем, что оптимизация FA является частью текущей практики. Я пытался передать смысл того, что было поставлено на карту в такой практике. Кроме того, я хотел бы отметить, что оптимизация — это не совсем то же самое, что минимизация — вы хотите минимизировать FA по отношению к примитивам, доступным в вашем наборе инструментов, а не просто сделать его FA с наименьшим количеством правил и т. д.
- person Bob Dalgleish; 18.05.2013
Я не понимаю, что вы имеете в виду в отношении примитивов, доступных в вашем наборе инструментов. Минимизация FA — это четко определенная задача, не зависящая от какой-либо реализации.
- person Fred Foo; 19.05.2013
Некоторые типы устройств дешевле в реализации или проще в компоновке, чем другие. Алгоритмы оптимизации, используемые в приложениях компоновки ИС, имеют встроенные в них правила и оптимизируются на основе технологии.
- person Bob Dalgleish; 19.05.2013
минимизированные автоматы всегда предпочтительнее: (1) эффективен (тот же алгоритм, если вы применяете к минимизированному автомату) (2a) нужно меньше элементов для реализации (2b) меньше по размеру (2c) дешевле (3) иногда очевиден ответ (причиной могут быть избыточные состояния ненужной сложности)
person
Grijesh Chauhan
schedule
19.05.2013
