Discusión:Autómata finito no determinista

ERROR en el ejemplo

El ejemplo que se muestra, que dice determinar si la cadena contiene un numero par de 0s o un numero par de 1s parece estar mal. Por ejemplo acepta la cadena 0 ya que termina en el estado final S3. No es necesario que el AFND termine en todos los estados finales, con que alcance uno es suficiente para aceptar la cadena segun se explica en la seccion funcionamiento. — El comentario anterior sin firmar es obra de Rodriros (disc. • contribs • bloq). Farisori » 14:35 15 abr 2013 (UTC)

Hola Rodriros. Hace muchos años que no veo este tema de los autómatas finitos en concreto, pero me parece que cuando se trata de autómatas no deterministas, entonces sí se puede asumir que el ejemplo está correcto. Es cuando hay determinismo que no se pueden dar este tipo de ambigüedades. A ver si alguien me corrige. Saludos, Farisori » 14:35 15 abr 2013 (UTC)

Hola, por si sirve de ayuda, el ejemplo dice que es la unión de dos autómatas, uno que acepta cadenas con cantidad pares de 1s y otro con cantidad pares de 0s. El problema es que el primero, además de aceptar cadenas con cantidad pares de 1s también acepta indeterminada cantidad de 0s y lo mismo ocurre con el que acepta cantidad pares de 0s, acepta indeterminada cantidad de 1s. Es por eso que la unión no da exactamente uno que acepta solamente cantidad pares de 0s o 1s. Yendo mas a la definición de autómatas no determinísticos, acepta una cadena sii termina en un estado incluido en F, y en este caso, con el ejemplo de la cadena 0 termina en S3 que está incluido en F. Espero no estar equivocándome y que sirva de ayuda. Saludos! --Rodriros (discusión) 15:33 15 abr 2013 (UTC)