Минимизация NFA - Википедия - NFA minimization

В теория автоматов (филиал теоретическая информатика ), Минимизация NFA это задача преобразования данного недетерминированный конечный автомат (NFA) в эквивалентную NFA с минимальным количеством состояний, переходов или и того, и другого. Хотя существуют эффективные алгоритмы для Минимизация DFA, Минимизация NFA NP-сложна. Эффективных (полиномиальных по времени) алгоритмов не известно. Тем не менее существуют алгоритмы, реализующие полезные функции, такие как Kameda-Weiner.[1] По этой теме опубликованы дополнительные исследования.[нужна цитата ]

Государственный минимальный NFA

В отличие от детерминированные конечные автоматы (DFA) минимальные NFA не могут быть уникальными. Может быть несколько NFA одного размера, которые принимают одинаковые входные последовательности (распознают одинаковые обычный язык ), но для которых нет NFA с меньшим количеством состояний, которые также распознают те же входные последовательности.

Рекомендации

  1. ^ Камеда, Цунехико "Тико"; Вайнер, Питер (август 1970). «О минимизации состояний недетерминированных конечных автоматов». Транзакции IEEE на компьютерах. IEEE. 100 (7): 617–627. Дои:10.1109 / T-C.1970.222994. Получено 2020-05-03.

внешняя ссылка

  • Модифицированная реализация C # Камеда-Вайнера (1970) [1]