Discusión:Autómata finito

Autómata finito es un artículo bueno, lo que significa que una versión suya cumple con los requisitos pertinentes. Si encuentras alguna forma de mejorarlo, eres bienvenido a hacerlo. Historial de eventos para este artículo Evaluación como artículo bueno realizada el 11 de abril de 2010 sobre esta versión. Resultado: APROBADO Fecha de aparición en la portada como artículo bueno: 5 de enero de 2013. Fecha de aparición en la portada como artículo bueno: 20 de enero de 2021.

correcciones antiguas

Creo que hay una errata en el texto, pues aparece en el artículo la siguiente afirmación:

"Si el estado inicial coincide con el final, entonces el lenguaje reconocido será aquel que está formado sólo por la palabra nula."

Y la verdad es que no estoy de acuerdo. Veamos este autómata, que reconoce cualquier cantidad de 0, con un único estado q, inicial y final:

Alfabeto = {0} Estado inicial = {q} Estado final = {q}

Función de transición:

Trans(q,0) = q

el lenguaje que reconoce este autómata es el de la expresión regular 0* = {palabra vacía, 0, 00, 000, 0000, ...} y no únicamente la palabra vacía, tal y como expresa el texto del artículo.

Espero que alguien aclare la duda.

---

Tu corrección es acertada.

--Toto 16:37 26 ene, 2005 (CET)

Estoy de acuerdo. --Nito 22:43 23 jun, 2005

yo no estos de acuerdo pienso que se sobre entiende que no hay trancición es decir no hay entrada de ningún valor sin embargo en lo que tu propones puede que haya o no estas añadiendo la entrada de datos y es solo cuando no entra nada en el autómata

La secuencia vacía

En el artículo se denotaba la secuencia vacía como $\lambda$, pero lo habitual es $\epsilon$.

Ver por ejemplo http://trevinca.ei.uvigo.es/~formella/doc/talf05/talf/node23.html

200.73.52.251 18:37 28 nov 2007 (CET)

Revisión SAB

• Arreglé un par de tonterías.
• Recuerdo que en la universidad (Ingeniería electrónica), cuando se tocó el tema de "máquinas de estado", estudiamos los "detectores de secuencia" y las "máquinas de Moore y Mealy". Le eché un ojo al artículo de la inglesa, y allá, efectivamente, clasifican las máquinas de estado en detectores de secuencia y transductores, los cuales a su vez se clasifican como máquinas de Moore y de Mealy (creo que la imagen del comienzo del artículo es una máquina de Mealy). ¿No debería mencionarse todo esto en este artículo?
• Comentario Probablemente sea por costumbre y nada más, pero pienso que la sección de historia debería ir al comienzo del artículo. ¿Qué piensan al respecto?

Es todo por ahora. Saludos. Racso ^¿¿¿??? 16:33 10 abr 2010 (UTC)

Hola Racso, muchas gracias por darte el trabajo. Sí, creo que la sección Historia queda mejor al comienzo. Con respecto a lo primero que dices, creo que en parte tienes razón... pero el artículo de la wikipedia en inglés no me parece buena comparación, pues está bastante desordenado, mezclando conceptos que hasta podrían tener que ver con UML... pero sí, quizá sería bueno a lo mejor incluir una sección final del tipo "Autómatas finitos modificados" o "Adaptaciones de autómatas finitos" (¿se te ocurre un nombre mejor?) donde se mencione la Máquina de Mealy y la Máquina de Moore, cuyas definiciones son un tanto diferentes y tienen otros propósitos, más de cómputo que de reconocimiento de lenguajes regulares... por eso no quise incorporarlas en un principio, pensando en WP:AB. Tú me dices, estoy abierto a las sugerencias ;) Saludos, Farisori » 17:40 10 abr 2010 (UTC)

Evidentemente tus conocimientos en el tema son muchísimo mayores que los míos, así que sólo daré sugerencias y tú me dirás a mí :P.

La verdad es que no sé de un buen nombre para la sección, ya que no sé exactamente qué son los detectores de secuencia y las máquinas de Mealy Moore. ¿Son adaptaciones, o, como tengo entendido, esos tres tipos abarcan todos los posibles autómatas? --Racso ^¿¿¿??? 19:48 10 abr 2010 (UTC)

En realidad, siendo un poco más específico, un transductor de estados finitos como dice en ese artículo, es una generalización de un autómata finito, pues además del alfabeto de entrada necesita de un alfabeto de salida. Le he estado dando vueltas y creo que es más sensato que en dicho artículo se mencione a los autómatas finitos, pero no sé si al revés sea tan necesario para efectos de un artículo bueno: (véase el punto 3.b). A lo más colocaría una sección muy breve donde se indique que existen generalizaciones que permiten ampliar las funcionalidades de estos autómatas, tales como los transductores... y señalar que ejemplos de estos últimos son las máquinas de Mealey y de Moore... ¿qué te parece? Saludos! Farisori » 20:37 10 abr 2010 (UTC)

Me parece estupendo. No te olvides de los "detectores de secuencia" (sección "Acceptors and recognizers" del artículo de en:wiki); supongo que también irían en la misma sección. ¡Salut! --Racso ^¿¿¿??? 21:02 10 abr 2010 (UTC)

Mmmm es que los detectores de secuencia son justamente los descritos en este artículo, en tanto a que son reconocedores de lenguajes regulares. En en.wikipedia están utilizando el mismo artículo para describir todo a distintos niveles.. en el fondo ese es un artículo para describir "autómatas de estados finitos" en el sentido de cualquier máquina computante con un número finito y discreto de estados, sin tanto poder como los autómata de pila o máquina de Turing... pero como te digo, se vuelve vago y habla de todo a la vez. Allá mencionan dos "tipos" de autómatas finitos: los reconocedores de lenguajes, y los transductores; sin embargo, estos últimos son una generalización de lo primero. La única distinción que me parece sensata hacer en un primer nivel es la de autómata finito determinista y no determinista, que allá sólo se señala muy por encima.

He quitado la imagen inicial pues estaba en inglés y en realidad más es lo que confunde de lo que clara, y reducido el índice, quitando los "Ejemplos" como secciones y dejándolos dentro de su sección respectiva. Ahora me dedicaré a la creación de la nueva sección. Saludos y muchas gracias! Farisori » 00:26 11 abr 2010 (UTC)

Hecho estimado, ya he incorporado la sección respectiva. Tú me dices. Quedo abierto a cualquier duda, exigencia, reclamo, ... Farisori » 01:32 11 abr 2010 (UTC)

Estupendo trabajo, Farisori. Ya aprobé el artículo; mis felicitaciones. --Racso ^¿¿¿??? 06:43 11 abr 2010 (UTC)

Hey Racso, mil gracias a ti por darte el trabajo de revisarlo y darme tan valiosos comentarios :-) me asombra la rapidez con que se dio todo en esta ocasión. Muchos saludos! Farisori » 08:21 11 abr 2010 (UTC)

AFND a AFD

Alguien que domine bien el tema de transformaciones defina bien si hay diferencias entre:

- AFND-ξ a AFD

- AFND a AFD.

He visto textos, en que la segunda opcion no existe. Alguien aclare mejor el tema. — El comentario anterior sin firmar es obra de Abel.orian (disc. • contribs • bloq). Farisori » 15:59 22 abr 2010 (UTC)

Hola: creo que queda bastante claro en el algoritmo mencionado que sí se puede... los AFND-ξ son un caso particular de los AFND; para pasar de AFND-ξ a AFD lo que se hace comúnmente es transformar primero el AFND-ξ a un AFND, y luego este a un AFD. Saludos, Farisori » 15:59 22 abr 2010 (UTC)

Se puede emplear exactamente el mismo algoritmo para convertir un AFND con o sin transiciones $\epsilon$ a un AFD. Cuando no hay transiciones $\epsilon$ entonces la parte en la que se calcula la cerradura-$\epsilon$ se puede omitir si se desea ya que resulta innecesaria. Esta distinción depende realmente de cómo se desee exponer el material y es cuestión de gustos.Robgomez (discusión) 15:36 21 jul 2010 (UTC)

AF y AFD son lo mismo

No tiene mucho caso hacer una sección especial para el AFD cuando la definición de AF (como está dada en el artículo) es la misma que la de un AFD. En ambos casos, para TODO par formado por un estado y un símbolo de entrada, siempre hay un único estado asociado. Esto se debe a que la función de transición debe estar definida para TODO $Q\times \Sigma$ debido a que si no estuviera definida en todo su dominio dejaría de ser función por definición. Para el caso particular en el que se desea omitir alguna transición que salga de un estado $q$ con cierto símbolo de entrada $a$ se debe emplear un autómata finito no determinístico (sin transiciones $\epsilon$) con $(q_{1},a)\mapsto \{\epsilon \}$; esto es común cuando se diseñan analizadores léxicos simples a mano.Robgomez (discusión) 15:46 21 jul 2010 (UTC)

Estoy de acuerdo, pero aún así creo que conviene manejar una sección particular para los deterministase, enfatizando su concepción de sistema determinista, en contraposición de su generalización no-determinista. Saludos, Farisori » 18:19 23 jul 2010 (UTC)

Posible error en la tercera figura

En mi modesta opinión, creo que hay un error en la tercera figura, en la que aparece el ejemplo de autómata que reconoce cadenas formadas por ceros y unos. En el texto de la figura, al final, pone: "El lenguaje regular que reconoce puede expresarse mediante la expresión regular (00|11|(01|10)(01|10))*". Sin embargo, al coincidir el estado inicial con el final está claro que también se reconoce la cadena formada por un solo uno, lo que no concuerda con la expresión regular mostrada. Talvez sea más correcto decir que reconoce cualquier cadena de ceros y unos en la que hay un número par de ceros (o incluso nulo). Obviamente también se reconocería la cadena vacía por ser el estado final igual al inicial.

Pido perdón por anticipado si es que me equivoco. Gracias por la atención y un saludo. — El comentario anterior sin firmar es obra de 93.156.65.50 (disc. • contribs • bloq). Farisori » 11:28 21 nov 2011 (UTC)

Hola, muchas gracias por la acotación. Tienes toda la razón en lo primero. Pero más aún, incluso se aceptarían palabras sin un número par de ceros (porque también se acepta por ejemplo 010). Por lo tanto mejor he retirado toda esa frase. Saludos, Farisori » 11:35 21 nov 2011 (UTC)