Lenguajes regulares planas

33

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.{X{una,si}# #una(X)+2# #si(X)0 0mod5 5}K5 5

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"?

Hendrik Jan
fuente
Además, el problema de decidir si un DFA plano puede reconocer un lenguaje normal parece difícil. Su capacidad de decisión es abierta, y tiene vínculos con problemas abiertos en la teoría de grafos.
Denis

Respuestas:

30

No es cierto que cada DFA para este lenguaje no sea plano:

Contraejemplo

Aquí hay un lenguaje que es verdaderamente no plano:

{X{σ1,...,σ6 6}El |yo=16 6yo# #σyo(X)0 0(mod7 7)}.
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.

Yuval Filmus
fuente
22

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.

Resumen. Se muestra que para cada autómata de estado finito existe un autómata no determinista equivalente con un gráfico de estado plano. Sin embargo, existen autómatas de estado finito sin autómata determinista equivalente con un gráfico de estado plano.

¡El ejemplo y la argumentación dados son exactamente los de Yuval en su respuesta!

Además, también consideran el alfabeto binario.

Hay un autómata determinista inherentemente no plano de 35 estados sobre un alfabeto de 2 letras.

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.

Teorema 9 (Jerarquía basada en el género). Hay idiomas regulares de género arbitrariamente grande.

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).

Proposición 7. Existen autómatas deterministas con un género estrictamente más bajo que el género de su autómata mínimo correspondiente.

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

Hendrik Jan
fuente