¿Existe una extensión de expresiones regulares que capture los lenguajes libres de contexto?

25

En muchos artículos que involucran gramáticas libres de contexto (CFG), los ejemplos de tales gramáticas presentados allí a menudo admiten caracterizaciones fáciles del lenguaje que generan. Por ejemplo:

SaaSb
S

genera {a2ibi|i0} ,

SaSb
SaaSb
S

genera {aibjij0} , y

SaSa
SbSb
S

genera {wwRw(a|b)} , o equivalente {((a|b))1((a|b))2p1=p2R} (donde p1 refiere a la parte capturada por (...)1 ).

Todos los ejemplos anteriores se pueden generar agregando índices ( ai ), restricciones simples en estos índices ( i>j ) y coincidencia de patrones con expresiones regulares. Esto me hace preguntarme si todos los lenguajes libres de contexto pueden ser generados por alguna extensión de las expresiones regulares.

¿Existe una extensión de expresiones regulares que pueda generar todos o algunos subconjuntos significativos de los lenguajes libres de contexto?

Alex ten Brink
fuente
3
Observe que agregar índices y restricciones es demasiado poderoso: podrá definir , que no es una CFL. anbncn
Shaull

Respuestas:

34

Sí hay. Defina una expresión sin contexto como un término generado por la siguiente gramática:

g::=ϵEmpty string|cCharacter c in alphabet Σ|ggConcatenation|Failing pattern|ggDisjunction|μα.gRecursive grammar expression|αVariable expression

Estos son todos los constructores para lenguajes regulares, excepto la estrella de Kleene, que se reemplaza por un operador general de punto fijo , y un mecanismo de referencia variable. (La estrella de Kleene no es necesaria, ya que se puede definir como g μ α .μα.g .)gμα.ϵgα

La interpretación de una expresión libre de contexto requiere tener en cuenta la interpretación de las variables libres. Por lo tanto, defina un entorno como un mapa de variables a idiomas (es decir, subconjuntos de ), y deje que sea ​​la función que se comporta como en todas las entradas excepto , y que devuelve el idioma para .Σ [ ρ | α : L ] ρ α L αρΣ[ρ|α:L]ραLα

Ahora, defina la interpretación de una expresión sin contexto de la siguiente manera:

[[ϵ]]ρ={ϵ}[[c]]ρ={c}[[g1g2]]ρ={w1w2|w1[[g1]]ρw2[[g2]]ρ}[[]]ρ=[[g1g2]]ρ=[[g1]]ρ[[g2]]ρ[[α]]ρ=ρ(α)[[μα.g]]ρ=nNLnwhereL0=Ln+1=Ln[[g]][ρ|α:Ln]

Usando el teorema de Knaster-Tarski, es fácil ver que la interpretación de es la menos fija de la expresión.μα.g

Es sencillo (aunque no del todo trivial) mostrar que puede dar una expresión sin contexto derivando el mismo lenguaje que cualquier gramática libre de contexto, y viceversa. La no trivialidad surge del hecho de que las expresiones sin contexto tienen puntos fijos anidados, y las gramáticas sin contexto le dan un solo punto fijo sobre una tupla. Esto requiere el uso del lema de Bekic, que dice precisamente que un punto fijo anidado se puede convertir en un único punto fijo sobre un producto (y viceversa). Pero esa es la única sutileza.

EDITAR: No, no conozco una referencia estándar para esto: lo resolví por mi propio interés. Sin embargo, es una construcción bastante obvia que estoy seguro de que se ha inventado antes. Algunos buscadores casuales en Google revelan el reciente documento de Context-Free Languages, Coalgebraically de Joost Winter, Marcello Bonsangue y Jan Rutten , donde dan una variante de esta definición (que requiere que todos los puntos fijos estén protegidos) que también llaman expresiones libres de contexto.

Neel Krishnaswami
fuente
Esto es bastante asombroso. ¿Hay un nombre estándar o referencia para esto?
Alex ten Brink
55
Arto Salomaa cubre esto en su libro "Idiomas formales" en 1973. Él los llama "expresiones regulares".
Tim Schaeffer
3

Hubo una pregunta estrechamente relacionada (y varias respuestas) en MathOverflow sobre los lenguajes cuyas funciones generadoras son holonómicas .

Curiosamente, la definición de Neel de la semántica de anterior corresponde exactamente a la prueba (constructiva) de la existencia de soluciones de especies para ecuaciones de especies recursivas a través del teorema de especies implícito. Desafortunadamente, su esquema de prueba también debe contener un error sutil, ya que hay casos en que las cosas se vuelven 'infinitas'. En otras palabras, hay una condición en el jacobiano de la transformación definida por la gramática como no singular que se necesita. Esta es probablemente la razón por la cual Bonsangue-Rutten requiere que los puntos fijos estén protegidos, como una forma de asegurar esta condición en el jacobiano.μ

Jacques Carette
fuente
AFAICT, Winter et al solo requieren cautela para garantizar que pueda tomar la derivada de Brzozowski de tomando la derivada de . [ μ α .μα.g[μα.g/α]g
Neel Krishnaswami
1

Recientemente hemos publicado los esquemas de un marco que hará exactamente eso. Mira en comp.compilers , donde envié una notificación junto con algunos enlaces.

Los nuevos desarrollos se basan en el Teorema de Chomsky-Schuetzenberger y pueden considerarse como la finalización de este resultado. Chomsky, él mismo, ha sido informado de los acontecimientos e indica un deseo de "ponerse al día".

Junto con este desarrollo, también establecemos la equivalencia de dos formulaciones separadas para expresiones libres de contexto, una que es una extensión / finalización de la forma de cálculo mu de "punto menos fijo" (originalmente por Gruska, Yntema y McWhirter) - que recibió una especie de formulación final en 2014, y la otra publicada en 2008.

NinjaDarth
fuente
44
Incluya toda la información relevante en la respuesta misma. "Buscar debajo de comp.compilers" es una respuesta poco útil ya, y será completamente inútil en un par de meses.
Emil Jeřábek apoya a Monica el
Eso está totalmente mal. Comp.compilers (a diferencia de este sitio y otros blogs, por cierto) se archiva permanentemente. Allí encontrará todos los detalles que necesita. Hay muchos enlaces que se pueden encontrar allí, también en el artículo publicado más recientemente. Además, a diferencia de los sitios de blogs, está abierto al exterior y es útil para un público mucho más amplio. No debería tener dificultades para encontrar algo en USENET, que es donde se deben abordar y debatir consultas como esta. Si tiene dificultades, aquí está el enlace. groups.google.com/forum/#!topic/comp.compilers/YCa5jHUR1iQ
NinjaDarth el
2
El problema no es que no esté archivado, sino que los archivos son vastos. Cuando mire los archivos ahora puedo encontrar tu publicación en algún lugar cerca de la parte superior, pero cuando alguien vea esta respuesta dentro de unos meses o años, no tendrán idea de dónde comenzar a cavar. Es arrogante y grosero hacer que los lectores hagan una búsqueda larga y poco confiable cuando puede señalarlos a una ubicación más específica. Ahora lo hice por ti. Tomó como 30 segundos. Podrías haberlo hecho tú mismo.
Emil Jeřábek apoya a Monica el