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 2n estados, exponencialmente más. Eso resulta que a veces construir un AFD de un AFND grande no es practicable.

This article is issued from Wikipedia - version of the Wednesday, March 13, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.