minimización de NFA

En la teoría de autómatas (una rama de la informática teórica ), la minimización de autómatas finitos no deterministas (AFND) consiste en transformar un autómata finito no determinista (AFND) dado en un AFND equivalente con un número mínimo de estados. Si bien existen algoritmos eficientes para la minimización de autómatas finitos deterministas (AFD ) , la minimización de AFND es PSPACE-completa . ^{[ 1 ]} No se conocen algoritmos eficientes ( de tiempo polinomial ) y, bajo la suposición estándar de que P ≠ PSPACE , no existe ninguno. El algoritmo más eficiente conocido es el algoritmo de Kameda-Weiner. ^{[ 2 ]}

A diferencia de los autómatas finitos deterministas , los autómatas finitos no deterministas (AFND) mínimos no tienen por qué ser únicos. Puede haber varios AFND no isomorfos con el mismo número (mínimo) de estados que acepten el mismo lenguaje regular , sin que exista un AFND equivalente más pequeño. ^{[ 2 ]}

Por ejemplo, el idioma que termina en${\displaystyle ab}$, denotado por${\displaystyle (a+b)^{*}ab}$sobre el alfabeto${\displaystyle \Sigma =\{a,b\}}$, no tiene ningún autómata finito no determinista (AFND) con menos de 3 estados. Existe un autómata finito determinista (AFD) mínimo de tres estados que rastrea determinísticamente cuánto del sufijo${\displaystyle ab}$se ha visto hasta ahora (ver imagen NFA 1). Además, hay un NFA mínimo no isomorfo para el mismo lenguaje que en cambio adivina de forma no determinista cada${\displaystyle a}$ya sea que comience el final${\displaystyle ab}$, aceptando si esa suposición es confirmada por el final de la cadena (NFA 2).

• Una implementación modificada en C# del método Kameda–Weiner (1970).