¿Puede un idioma tener más de un DFA?

17

Por ejemplo, cuando consideramos un DFA que permite que las cadenas no tengan subcadenas 00o que 11yo pueda producir los siguientes dos DFA:

ingrese la descripción de la imagen aquí

automata finite-automata Madhuri
fuente

Respuestas:

37

En primer lugar, su DFA izquierdo es incorrecto; acepta, por ejemplo, 011.

En segundo lugar, los DFA pueden minimizarse canónicamente , por lo que, en ese sentido, siempre puede encontrar un DFA canónico para un idioma determinado.

Pero en general, hay infinitos DFA diferentes para cada idioma, por lo que puede obtener diferentes respuestas correctas.

Shaull
fuente
Y eso es incluso infinitamente hasta el isomorfismo.
G. Bach
N
¿Infinitos muchos DFA diferentes incluso para idiomas finitos?
Bergi
1
@Bergi: Ciertamente, puede agregar tantos estados redundantes como desee. Esto puede sonar "tonto", y de hecho no tiene sentido cuando construyes un autómata tú mismo. Sin embargo, muchas veces los autómatas se construyen mediante la traducción de algún otro formalismo (por ejemplo, la determinación de NFA), en cuyo caso es muy probable que obtenga estados redundantes.
Shaull
@Shaull: ¿Quieres decir con transiciones ε o estados inalcanzables? OK, no los consideré.
Bergi