Construcción de conjunto potencia

En la teoría de la computación, la construcción de conjunto potencia es un método estándar para convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) que reconoce el mismo lenguaje formal. En la teoría es importante porque establece que los AFNDs aunque son más flexibles, no pueden reconocer ningún lenguaje que un AFD no pueda reconocer. También es importante porque se puede usar para convertir un AFND que es más fácil de construir a un AFD que es más fácil de ejecutar. Sin embargo si el AFND tiene $n$ estados, el AFD resultante podría tener hasta $2^{n}$ estados, exponencialmente más. Eso resulta que a veces construir un AFD de un AFND grande no es practicable.

• Datos: Q2106494