¿Alguien puede proporcionar un ejemplo de dos autómatas no deterministas (NFA) mínimos equivalentes (que reconocen el mismo lenguaje) que no son isomorfos?
fl.formal-languages
automata-theory
Guy Vidal-Naquet
fuente
fuente
Respuestas:
Ver el artículo (posdata)
Arnold, Dicky, Nivat. Una nota sobre autómatas no deterministas mínimos
fuente
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.L6 an n
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.
fuente