Minimalizace NFA - NFA minimization - Wikipedia

v teorie automatů (pobočka teoretická informatika ), Minimalizace NFA je úkolem transformace dané nedeterministický konečný automat (NFA) na ekvivalentní NFA, která má minimální počet stavů, přechodů nebo obojí. I když existují účinné algoritmy Minimalizace DFA „Minimalizace NFA je NP-tvrdá. Nejsou známy žádné efektivní algoritmy (polynomiální čas). Přesto existují algoritmy, které implementují užitečné funkce, jako je Kameda-Weiner.[1] Na toto téma byl publikován další výzkum.[Citace je zapotřebí ]

Uveďte minimální NFA

Na rozdíl od deterministické konečné automaty (DFA), minimální NFA nemusí být jedinečné. Může existovat několik NFA stejné velikosti, které přijímají stejné vstupní sekvence (rozpoznávají stejné běžný jazyk ), ale pro které neexistují žádné NFA s menším počtem stavů, které také rozpoznávají stejné vstupní sekvence.

Reference

  1. ^ Kameda, Tsunehiko "Tiko"; Weiner, Peter (srpen 1970). „O minimalizaci stavu nedeterministických konečných automatů“. Transakce IEEE na počítačích. IEEE. 100 (7): 617–627. doi:10.1109 / T-C.1970.222994. Citováno 2020-05-03.

externí odkazy

  • Upravená implementace C # Kameda-Weiner (1970) [1]