Autómatas finitos no deterministas mínimos no isomórficos

Respuestas:

11

Ver el artículo (posdata)

Arnold, Dicky, Nivat. Una nota sobre autómatas no deterministas mínimos

ingrese la descripción de la imagen aquí

Hendrik Jan
fuente
1
¡Gracias por compartir! Su artículo incluye un buen ejemplo. :)
Michael Wehar
4

En una línea diferente: el conjunto de cadenas de la forma , donde no es un múltiplo de 6 tiene dos NFA mínimos muy diferentes. L6annDos NFA mínimos por $ L_6 $.

Uno de ellos es básicamente el DFA mínimo, el otro adivina si no es un múltiplo de 2 o si no es un múltiplo de 3.

Thomas S
fuente