En mi clase, un estudiante preguntó si todos los autómatas finitos podían dibujarse sin cruzar bordes (parece que todos mis ejemplos lo hicieron). Por supuesto, la respuesta es negativa, el autómata obvio para el idioma tiene la estructura de K_5 , el gráfico completo en cinco nodos . Yuval ha mostrado una estructura similar para un lenguaje relacionado.
Mi pregunta es la siguiente: ¿cómo mostramos que cada autómata de estado finito para este lenguaje no es plano? Con caracterizaciones similares a Myhill-Nerode, probablemente se pueda establecer que la estructura del lenguaje está presente en el diagrama, pero ¿cómo podemos precisar esto?
Y si eso se puede hacer, ¿hay una caracterización de los "lenguajes regulares planos"?
regular-languages
finite-automata
planar-graphs
Hendrik Jan
fuente
fuente
Respuestas:
No es cierto que cada DFA para este lenguaje no sea plano:
Aquí hay un lenguaje que es verdaderamente no plano:{ x ∈ { σ1, ... , σ6 6}∗∣∣∣∑i = 16 6yo #σyo( x ) ≡ 0( mod7 ) } .
Tome cualquier FSA plana para este idioma. Si eliminamos todos los estados inalcanzables, aún obtenemos un gráfico plano. Cada estado alcanzable tiene seis bordes salientes distintos , lo que contradice el hecho conocido de que cada gráfico plano tiene un vértice de grado como máximo cinco.
fuente
El concepto ha sido investigado antes. (Una vez que sepa la respuesta, búsquela en Google ...)
Primero hay un trabajo antiguo de Book y Chandra, con el siguiente resumen.
¡El ejemplo y la argumentación dados son exactamente los de Yuval en su respuesta!
Además, también consideran el alfabeto binario.
Bonfante y Deloup continúan este trabajo recientemente. Consideran las incrustaciones topológicas. Informalmente, el género de un gráfico es el número de agujeros que se deben agregar para incrustar el gráfico en una superficie sin cruzar bordes. Las gráficas con género cero son planas. Entonces, el género de un idioma es el género mínimo de los autómatas para el idioma.
En la sección "Autómatas de estado mínimo versus autómatas de género mínimo" se encuentra el resultado, cuya prueba es el primer ejemplo dado por Yuval (diez estados para hacer que el lenguaje K5 de cinco estados sea plano).
G.Bonfante, F.Deloup: El género de los lenguajes regulares, Mathematical Structures in Computer Science, 2018. doi 10.1017 / S0960129516000037 . También ArXiv 1301.4981 (2013)
RV Book, AK Chandra, Autómatas inherentemente no planos, Acta informatica 6 (1976) doi 10.1007 / BF00263745
fuente