b'\n_START_ARTICLE_\nAut\xc3\xb3mata finito\n_START_PARAGRAPH_\nUn aut\xc3\xb3mata finito (AF) o m\xc3\xa1quina de estado finito es un modelo computacional que realiza c\xc3\xb3mputos en forma autom\xc3\xa1tica sobre una entrada para producir una salida._NEWLINE_Este modelo est\xc3\xa1 conformado por un alfabeto, un conjunto de estados finito, una funci\xc3\xb3n de transici\xc3\xb3n, un estado inicial y un conjunto de estados finales. Su funcionamiento se basa en una funci\xc3\xb3n de transici\xc3\xb3n, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el aut\xc3\xb3mata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptaci\xc3\xb3n, que representa la salida._NEWLINE_La finalidad de los aut\xc3\xb3matas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales m\xc3\xa1s simples seg\xc3\xban la Jerarqu\xc3\xada de Chomsky.\n_START_SECTION_\nHistoria\n_START_PARAGRAPH_\nEl origen de los aut\xc3\xb3matas finitos probablemente se remonta a su uso impl\xc3\xadcito en m\xc3\xa1quinas electromec\xc3\xa1nicas, desde principios del siglo XX.\xe2\x80\x8b Ya en 1907, el matem\xc3\xa1tico ruso Andr\xc3\xa9i M\xc3\xa1rkov formaliz\xc3\xb3 un proceso llamado cadena de Markov, donde la ocurrencia de cada evento depende con una cierta probabilidad del evento anterior.\xe2\x80\x8b Esta capacidad de "recordar" es utilizada posteriormente por los aut\xc3\xb3matas finitos, que poseen una memoria primitiva similar, en que la activaci\xc3\xb3n de un estado tambi\xc3\xa9n depende del estado anterior, as\xc3\xad como del s\xc3\xadmbolo o palabra presente en la funci\xc3\xb3n de transici\xc3\xb3n._NEWLINE_Posteriormente, en 1943, surge una primera aproximaci\xc3\xb3n formal de los aut\xc3\xb3matas finitos con el modelo neuronal de McCulloch-Pitts. Durante la d\xc3\xa9cada de 1950 prolifera su estudio, frecuentemente llam\xc3\xa1ndoseles m\xc3\xa1quinas de secuencia; se establecen muchas de sus propiedades b\xc3\xa1sicas, incluyendo su interpretaci\xc3\xb3n como lenguajes regulares y su equivalencia con las expresiones regulares.\xe2\x80\x8b Al final de esta d\xc3\xa9cada, en 1959, surge el concepto de aut\xc3\xb3mata finito no determinista en manos de los inform\xc3\xa1ticos te\xc3\xb3ricos Michael O. Rabin y Dana Scott.\xe2\x80\x8b_NEWLINE_En la d\xc3\xa9cada de 1960 se establece su conexi\xc3\xb3n con las series de potencias y los sistemas de sobreescritura.\xe2\x80\x8b Finalmente, con el desarrollo del sistema operativo Unix en la d\xc3\xa9cada de 1970, los aut\xc3\xb3matas finitos encuentran su nicho en el uso masivo de expresiones regulares para fines pr\xc3\xa1cticos, espec\xc3\xadficamente en el dise\xc3\xb1o de analizadores l\xc3\xa9xicos (comando lex) y la b\xc3\xbasqueda y reemplazo de texto (comandos ed y grep).\xe2\x80\x8b A partir de ese tiempo, los aut\xc3\xb3matas finitos tambi\xc3\xa9n se comienzan a utilizar en sistemas din\xc3\xa1micos.\xe2\x80\x8b\n_START_SECTION_\nFuncionamiento\n_START_PARAGRAPH_\nEn el comienzo del proceso de reconocimiento de una cadena de entrada, el aut\xc3\xb3mata finito se encuentra en el estado inicial y a medida que procesa cada s\xc3\xadmbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la funci\xc3\xb3n de transici\xc3\xb3n. Cuando se ha procesado el \xc3\xbaltimo de los s\xc3\xadmbolos de la cadena de entrada, el aut\xc3\xb3mata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado de aceptaci\xc3\xb3n, entonces la cadena pertenece al lenguaje reconocido por el aut\xc3\xb3mata; en caso contrario, la cadena no pertenece a dicho lenguaje._NEWLINE_Note que el estado inicial  de un aut\xc3\xb3mata finito siempre es \xc3\xbanico, en tanto que los estados finales pueden ser m\xc3\xa1s de uno, es decir, el conjunto  puede contener m\xc3\xa1s de un elemento. Tambi\xc3\xa9n puede darse el caso de que un estado final corresponda al mismo estado inicial.\n_START_SECTION_\nEquivalencias entre aut\xc3\xb3matas finitos\n_START_PARAGRAPH_\nSe dice que dos aut\xc3\xb3matas finitos son equivalentes, si ambos reconocen el mismo lenguaje regular._NEWLINE_Toda expresi\xc3\xb3n regular (que define a su vez un lenguaje regular) puede ser expresada como un aut\xc3\xb3mata finito determinista,\xe2\x80\x8b y viceversa.\xe2\x80\x8b Dada una expresi\xc3\xb3n regular, es posible construir un AFND-\xce\xb5 que reconozca dicho lenguaje, por ejemplo mediante el algoritmo de Thompson. Luego, todo AFND-\xce\xb5 puede transformarse en un AFND equivalente, as\xc3\xad como todo AFND puede transformarse en un AFD equivalente, mediante el m\xc3\xa9todo llamado construcci\xc3\xb3n de conjunto potencia. As\xc3\xad, por transitividad, para cualquier aut\xc3\xb3mata finito no determinista siempre existe un aut\xc3\xb3mata finito determinista equivalente, y viceversa.\xe2\x80\x8b_NEWLINE_Normalmente en el dise\xc3\xb1o de aut\xc3\xb3matas finitos, lo primero que se hace es construir un AFND-\xce\xb5, que es el m\xc3\xa1s sencillo de construir, por poseer menos restricciones en su funci\xc3\xb3n de transiciones. Luego dicho aut\xc3\xb3mata se reduce a un AFND, y finalmente a un AFD, el cual por sus caracter\xc3\xadsticas deterministas ya puede ser implementado sin problemas utilizando un lenguaje de programaci\xc3\xb3n.\n_START_SECTION_\nGeneralizaciones de aut\xc3\xb3matas finitos\n_START_PARAGRAPH_\nExisten diversas generalizaciones posibles de hacer sobre los aut\xc3\xb3matas finitos, para aumentar su uso y expresividad. As\xc3\xad, por ejemplo, se definen los transductores de estados finitos como aut\xc3\xb3matas finitos que est\xc3\xa1n dotados adem\xc3\xa1s de un alfabeto de salida, distinto al de entrada, y que pueden poseer m\xc3\xa1s de un estado inicial.\xe2\x80\x8b Las m\xc3\xa1quinas de Moore y m\xc3\xa1quinas de Mealy son conocidos ejemplos de transductores, que se utilizan sobre todo para modelar sistemas secuenciales.\xe2\x80\x8b\xe2\x80\x8b_NEWLINE_Es incluso posible aumentar el poder de c\xc3\xb3mputo de un aut\xc3\xb3mata finito, permitiendo un alfabeto adicional sobre \xc3\xa9ste, que act\xc3\xbae sobre una memoria de tipo pila para ser considerada en cada transici\xc3\xb3n. Esta es la idea utilizada por los llamados aut\xc3\xb3matas con pila, los cuales son capaces de reconocer lenguajes libres de contexto, que est\xc3\xa1n un nivel por sobre los lenguajes regulares en la Jerarqu\xc3\xada de Chomsky.\xe2\x80\x8b'