Algoritmo para probar si un idioma es regular

¿Existe un algoritmo / procedimiento sistemático para evaluar si un idioma es regular?

En otras palabras, dado un idioma especificado en forma algebraica (piense en algo como ), pruebe si el idioma es regular o no. Imagine que estamos escribiendo un servicio web para ayudar a los estudiantes con todas sus tareas; el usuario especifica el idioma y el servicio web responde con "regular", "no regular" o "No sé". (Nos gustaría que el servicio web responda "No sé" con la menor frecuencia posible). ¿Hay algún buen enfoque para automatizar esto? ¿Es esto manejable? ¿Es decidible (es decir, es posible garantizar que nunca necesitemos responder "No sé")? ¿Existen algoritmos razonablemente eficientes para resolver este problema y poder proporcionar una respuesta que no sea "no sé" $L=\{a^n b^n : n \in \mathbb{N}\}$

El método clásico para demostrar que un idioma no es regular es el lema de bombeo. Sin embargo, parece que requiere una visión manual en algún momento (por ejemplo, para elegir la palabra que se va a bombear), por lo que no tengo claro si esto puede convertirse en algo algorítmico.

Un método clásico para demostrar que un lenguaje es regular sería utilizar el teorema de Myhill-Nerode para derivar un autómata de estado finito. Esto parece un enfoque prometedor, pero requiere la capacidad de realizar operaciones básicas en idiomas en forma algebraica. No me queda claro si existe una forma sistemática de realizar simbólicamente todas las operaciones que puedan ser necesarias, en idiomas en forma algebraica.

Para hacer esta pregunta bien planteada, debemos decidir cómo el usuario especificará el idioma. Estoy abierto a sugerencias, pero estoy pensando en algo como esto:

L = {E : S}

$L = \{E : S\}$

donde es una expresión de palabras y es un sistema de desigualdades lineales sobre las variables de longitud, con las siguientes definiciones: $E$ $S$

Cada uno de es una expresión de palabras. (Estos representan variables que pueden tomar cualquier palabra en .) $x,y,z,\dots$ $\Sigma^*$
Cada uno de es una expresión de palabras. (Aquí representa el reverso de la cadena .) $x^r,y^r,z^r,\dots$ $x^r$ $x$
Cada uno de es una expresión de palabras. (Implícitamente, , por lo que representan un solo símbolo en el alfabeto subyacente). $a,b,c,\dots$ $\Sigma=\{a,b,c,\dots\}$ $a,b,c,\dots$
Cada uno de es una expresión de palabra, si es una variable de longitud. $a^\eta,b^\eta,c^\eta,\dots$ $\eta$
La concatenación de expresiones de palabras es una expresión de palabras.
Cada uno de es una variable de longitud. (Representan variables que pueden tomar cualquier número natural). $m,n,p,q,\dots$
Cada uno de es una variable de longitud. (Estos representan la longitud de una palabra correspondiente). $|x|,|y|,|z|,\dots$

Esto parece lo suficientemente amplio como para manejar muchos de los casos que vemos en los ejercicios de libros de texto. Por supuesto, puede sustituir cualquier otro método textual para especificar un idioma en forma algebraica, si tiene una mejor sugerencia.

Todavía no he tenido tiempo de pensar mucho sobre su elección de expresiones de lenguaje. ¿Aproximadamente qué tipo de idiomas cubre? Si agrega la restricción de que una variable de palabra se produce solo una vez, ¿todos estos idiomas están libres de contexto?

Gilles 'SO- deja de ser malvado'

¿Quizás puedas intentar escribir con una gramática? Como y, ¿es sucintamente lo que usted describe?

E

$E$

E ::= c^{η} ∣ x ∣ E E ∣ E^{r}

$E ::= c^η ∣ x ∣ EE ∣ E^r$

η ::= n ∣ | x |

$η ::= n ∣ |x|$

jmad

Puede expresar para que esto vaya más allá de los lenguajes libres de contexto. Aún así, sospecho que el problema es al menos tan difícil como decidir si una gramática libre de contexto define un lenguaje regular.

{a^{n} b^{n} c^{n} ∣ n \in N}

$\{a^nb^nc^n \mid n\in\mathbb{N}\}$

Gilles 'SO- deja de ser malvado'

@jmad, sí, eso sería perfectamente razonable. No estoy casado con esta elección de expresiones del lenguaje: siéntase libre de elegir otra cosa, si ve algo más apropiado. Gilles, gran ángulo de ataque! (Para los espectadores, hay resultados conocidos que muestran que probar si una gramática arbitraria sin contexto define un lenguaje regular es indecidible). Si el problema es indecidible, sugiero que modifiquemos el problema para permitir que el servicio web responda "No 'No sé ", y luego solicite un algoritmo que responda" No sé "tan raramente como sea posible.

Esta clase no está cerrada bajo la estrella de Kleene, ¿verdad? ¿Puedes expresar paréntesis equilibrados?

Gilles 'SO- deja de ser malvado'

Respuestas:

La respuesta es no. Decidir si una gramática libre de contexto dada genera un lenguaje regular es un problema indecidible.

Actualización . Di esta respuesta negativa a la pregunta general.

Dado un idioma especificado en forma algebraica, pruebe si el idioma es regular o no

dado que los lenguajes sin contexto son soluciones de ecuaciones algebraicas en los lenguajes: vea el Capítulo II, Teoremas 1.4 y 1.5 en el libro de J. Berstel Transductions and Context-Free Languages .

Sin embargo, la misma pregunta es decidible para lenguajes deterministas libres de contexto, un resultado no trivial debido a Stearns [1] y mejorado por Valiant [2]:
[1] RE Stearns, una prueba de regularidad para máquinas pushdown, información y control 11 323- 340 (1967). DOI: 10.1016 / S0019-9958 (67) 90591-8.
[2] LG Valiant. Regularidad y problemas relacionados con los autómatas deterministas de empuje J. ACM 22 (1975), pp. 1-10.

Hay otro resultado positivo, más cercano a las especificaciones dadas en la segunda parte de la pregunta. Recuerde que los subconjuntos semilineales de son exactamente los conjuntos definibles en la aritmética de Presburger. También están los subconjuntos racionales de . En particular, un subconjunto de definido por inecuaciones lineales es racional. Ahora, dado un subconjunto racional de , es decidible si el lenguaje es regular. De hecho, se sabe [Ginsburg-Spanier] que es regular si y solo si es un subconjunto reconocible de $\mathbb{N}^k$ $\mathbb{N}^k$ $\mathbb{N}^k$ $R$ $\mathbb{N}^k$

L (R) = {u_{1}^{n_{1}} \dots u_{k}^{n_{k}} ∣ (n_{1}, . . ., n_{k}) \in R}

$L(R) = \{ u_1^{n_1} \dotsm u_k^{n_k} \mid (n_1, ...,n_k) \in R \}$

L (R)

$L(R)$

R

$R$

N^{k}

$\mathbb{N}^k$ y es decidible [Ginsburg-Spanier] si un subconjunto racional dado de es reconocible.

N^{k}

$\mathbb{N}^k$

S. Ginsburg y EH Spanier., Semigrupos, fórmulas de Presburger e idiomas , Pacific J. Math. 16 (1966), 285-296.

S. Ginsburg y EH Spanier. Conjuntos regulares limitados , Proc. de la matemática estadounidense. Soc. 17 , 1043-1049 (1966).

Esto no resuelve la segunda parte de la pregunta, que podría ser indecidible debido a las variables de la palabra, pero da un fragmento razonable para comenzar.

J.-E. Alfiler
fuente

(a) Pedantic nit: no me queda claro si la sintaxis algebraica anterior es lo suficientemente general como para expresar todas las gramáticas libres de contexto (como Gilles y yo insinuamos en los comentarios), por lo que no está del todo claro si ese resultado en particular se aplica aquí . (b) Más importante: considere la declaración del problema adecuadamente ajustada para que el servicio web pueda responder "No sé", y nos gustaría encontrar un algoritmo que responda "No sé" tan raramente como sea posible. Anteriormente sugerí esto en los comentarios; Editaré la pregunta para aclarar esto en la pregunta misma.

Sospecho que puede adaptar la prueba, pero el resultado no sigue. Creo que hay lenguajes libres de contexto que no se pueden expresar en este formalismo: por ejemplo, ¿cómo se expresan los paréntesis equilibrados? La clase de idiomas no está cerrada bajo la estrella de Kleene, ¿verdad?

Gilles 'SO- deja de ser malvado'

@Gilles, sí, pensé en eso. No tengo claro de inmediato cómo adaptar la prueba. La prueba estándar de que es indecidible saber si una gramática libre de contexto es regular es a través del teorema de Greibach. Sin embargo, no me parece que esta clase de lenguajes satisfaga las premisas del teorema de Greibach (no parece probable que se cierre bajo concatenación con conjuntos regulares y cerrado bajo unión). Tal vez hay algún otro enfoque de prueba con el que no estoy familiarizado. Estoy de acuerdo, no está claro cómo expresar el lenguaje de paréntesis equilibrados en esta forma algebraica.

Acabo de agregar las referencias.

J.-E.

Su publicación no responde a la pregunta, porque aborda una clase diferente de idiomas. Las formas algebraicas permitidas aquí (con una sola expresión de palabra) son (hasta donde podemos decir) no tan generales como las formas algebraicas necesarias para expresar lenguajes arbitrarios sin contexto. Podría ser el caso de que para la intersección de los dos, el problema es decidible.

Gilles 'SO- deja de ser malvado'