Минимизация NFA

В теории автоматов (раздел теоретической информатики ) минимизация NFA — это задача преобразования данного недетерминированного конечного автомата (NFA) в эквивалентный NFA, который имеет минимальное количество состояний, переходов или того и другого. существуют эффективные алгоритмы Хотя для минимизации DFA , минимизация NFA является PSPACE-полной . ^[1] Эффективных алгоритмов (с полиномиальным временем) неизвестно, и при стандартном предположении P ≠ PSPACE их не существует. Наиболее эффективным известным алгоритмом является алгоритм Камеды-Вайнера. ^[2]

Неединственность минимального NFA

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

Ссылки

^ Цзян, Тао; Равикумар, Б. (1993), «Минимальные проблемы NFA сложны» , SIAM Journal on Computing , 22 (6): 1117–1141, doi : 10.1137/0222067
^ Камеда, Цунехико; Вайнер, Питер (август 1970 г.). «О государственной минимизации недетерминированных конечных автоматов» . Транзакции IEEE на компьютерах . С-19 (7). ИИЭР : 617–627. дои : 10.1109/TC.1970.222994 . S2CID 31188224 . Проверено 3 мая 2020 г.

Внешние ссылки

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

[TaoRavikumar93-1] Цзян, Тао; Равикумар, Б. (1993), «Минимальные проблемы NFA сложны» , SIAM Journal on Computing , 22 (6): 1117–1141, doi : 10.1137/0222067

[Kameda-Weiner_1970-2] Камеда, Цунехико; Вайнер, Питер (август 1970 г.). «О государственной минимизации недетерминированных конечных автоматов» . Транзакции IEEE на компьютерах . С-19 (7). ИИЭР : 617–627. дои : 10.1109/TC.1970.222994 . S2CID 31188224 . Проверено 3 мая 2020 г.

[1]

[2]