Complejidad de la intersección de lenguajes regulares como gramáticas libres de contexto

Dadas las expresiones regulares , ¿existen límites no triviales en el tamaño de la gramática libre de contexto más pequeña para ? $R_1, \dots, R_n$ $R_1 \cap \cdots \cap R_n$

fl.formal-languages regular-language context-free Max
fuente

??? tratando de visualizar esto ¿hay algún truco? La intersección de es regular. uno puede encontrar el DFA mínimo (recuento de estados de wrt) a través de métodos estándar que también es un CFG.

R_{n}

$R_n$

vzn

@vzn: tienes razón. El problema es que este DFA, y por lo tanto el CFG, puede ser muy grande. Me pregunto si se puede usar la potencia extra de los CFG para obtener una descripción más sucinta de la intersección.

Max

conjetura no. sospecha que cada CFL que reconoce (es decir, es equivalente a) un RL no utiliza su pila o puede convertirse en uno que no aumente los estados, y el mínimo de ese PDA (recuento de estados wrt) es del mismo tamaño que el mínimo DFA Nunca he escuchado / visto una prueba de esto. tal vez no es difícil? una pregunta más simple, ¿hay alguna PDA que reconozca un RL que sea más pequeño que el DFA? No pienses.

vzn

@vzn: Conjetura útil, pero falsa: deje que sea el subconjunto de los idiomas Dyck en dos tipos de paréntesis donde la profundidad máxima de anidación es . Hay un CFG para de tamaño , pero el DFA mínimo (incluso, creo, el NFA mínimo) tiene el tamaño .

L_{k}

$L_k$

k

$k$

L_{k}

$L_k$

O (k)

$O(k)$

O (2^{k})

$O(2^k)$

Max

Los idiomas Dyck son CFL pero no RL ...? pero ves que estás limitando la profundidad máxima de anidación ... entonces, ¿puedes construir ese mismo lenguaje con intersecciones RL? ¿Cuál / dónde es la prueba de que el DFA mínimo es tan grande? ¿Es eso

O (2^{k})

$O(2^k)$ estados ? no define un criterio de minimidad ni en otro lugar y toma los estados como un caso natural, pero no es el único.

vzn

Respuestas:

Esta es una gran pregunta y realmente está dentro de mis intereses. Me alegra que lo hayas preguntado Max.

Deje que se den DFA con como máximo estados cada uno. Sería bueno si existiera un PDA con muchos estados sub-exponencialmente que acepten la intersección de los idiomas de DFA. Sin embargo, sugiero que tal PDA no siempre exista. $n$ $O(n)$

Considere el lenguaje de copia. Ahora, limítelo a copiar cadenas de longitud n.

Formalmente, considere -copy . $n$ $:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$

Podemos representar -copy como la intersección de DFA de tamaño como máximo . Sin embargo, el DFA más pequeño que acepta -copy tiene estados. $n$ $n$ $O(n)$ $n$ $2^{\Omega(n)}$

Del mismo modo, si nos limitamos a un alfabeto de pila binario, sospecho que el PDA más pequeño que acepta -copy tiene exponencialmente muchos estados. $n$

PD No dude en enviarme un correo electrónico si desea discutir más. :)

Michael Wehar
fuente

No creo que pueda haber límites inferiores o superiores no triviales.
Para límites inferiores, considere el idioma para una fija . El tamaño de la gramática libre de contexto más pequeña es logarítmico en el tamaño de la expresión regular de , mientras que el tamaño del autómata más pequeño para es lineal en el tamaño de la regular de . Esta diferencia exponencial se mantiene igual si intersectamos con otros lenguajes similares. Para los límites superiores, considere un lenguaje que consiste exactamente en una secuencia deBruijn de longitud . Se sabe que el tamaño de una gramática más pequeña para $L_1 = \{ a^{2^k} \}$ $k$ $L_1$ $L_1$ $L_1$ $L_1$
$L_2$ $n$ $L_2$ es el peor de los casos, es decir, , por lo que la diferencia con el autómata "más pequeño" para es simplemente un factor logarítmico, proposición 1 en $O\left( \frac{n}{\log n} \right)$ $L_2$

D. Hucke, M. Lohrey, E. Noeth Construyendo gramáticas de árboles pequeños y pequeños circuitos para fórmulas , que aparecerán en FSTTCS 2014

Un límite inferior o superior general no trivial contradeciría esos resultados, ya que lo que es cierto para la intersección de idiomas debe ser cierto para la intersección de idioma. $n$ $1$

john_leo
fuente

La observación sobre el tamaño de la gramática más pequeña para la secuencia única deBruijn es bastante interesante. ¿Podría por favor proporcionar una referencia? Gracias.

Michael Wehar

Además, podría estar equivocado, pero parece que solo abordó el problema para una sola expresión regular (en lugar de un producto de expresiones regulares).

Michael Wehar

@MichaelWehar Sí, solo consideré una sola expresión regular. Porque si debe ser cierto para la intersección de idiomas, entonces ciertamente debe ser cierto para la intersección trivial. No sé cómo reformular la pregunta para excluir estos casos. Agregué la referencia, debería haberlo hecho de inmediato, lo siento.

n

$n$

john_leo

¡Gracias! Pudiste describir un ejemplo específico. Aquí hay un comentario simple que conduce a la existencia de tales ejemplos. Deje n ser dado. Hay 2 ^ n cadenas de longitud n. Además, no hay más de 2 ^ n máquinas de Turing con a lo sumo n / log (n) estados. Por lo tanto, alguna cadena x de longitud n tal que ninguna máquina de Turing con menos de n / log (n) acepte el idioma {x}. Por lo tanto, {x} es aceptado por un DFA con n estados y no puede ser aceptado por un PDA con menos de n / log (n) estados.

Michael Wehar

Permítanme apoyar el juicio de Michael, esta es una pregunta interesante. La idea principal de Michael se puede combinar con un resultado de la literatura, proporcionando así un límite inferior similar con una prueba rigurosa.

Me referiré a los límites en el tamaño de CFG en términos del número total de símbolos alfabéticos en las expresiones regulares. Deje que este número se denote por . (Como señaló john_leo, no encontraremos ningún límite útil en términos del número de expresiones regulares que participan en la intersección). $n$ $k$

Ni el OP ni Michael consideraron necesario mencionar esto, pero se puede probar fácilmente un límite superior de (en el número de estados) para convertir una intersección de expresiones regulares en un NFA. Para el registro, aquí está: Convierta las expresiones regulares en autómatas de Glushkov, que no son retornables. Luego aplique la construcción del producto para obtener un NFA para la intersección de estos idiomas. (Supongo que uno puede mejorar el límite a o menos.) Un NFA de estado se puede convertir en una gramática lineal derecha (que es un caso especial de un CFG) de tamaño (si medimos el tamaño de la gramática como el número total de símbolos en los lados izquierdo y derecho de las producciones), dando así el tamaño $2^{k+1}$ $2^k+1$ $s$ $O(s^2)$ $O(4^{k})$ . Este límite, por supuesto, suena horrible si tiene en mente aplicaciones prácticas. Puede que valga la pena intentar probar un límite mejor utilizando la complejidad de transición no determinista en lugar de la complejidad de estado no determinista para estimar el tamaño de la NFA.

La otra parte es encontrar un lenguaje testigo que pueda expresarse sucintamente como la intersección de las expresiones regulares, pero que es necesariamente engorroso de describir con un CFG. (Aquí necesitamos establecer un límite inferior en el tamaño de todos los CFG que generan el lenguaje, de los cuales puede haber infinitos). El siguiente argumento da un límite inferior. $2^{\Omega(\sqrt{k}/\log k)}$

Considere el lenguaje finito , donde denota la inversión de . Entonces se puede expresar como la intersección de las siguientes expresiones regulares : $L_n = \{\,ww^Rw \in \{a,b\}^*\mid |w|=n\,\}$ $w^R$ $w$ $L_n$ $2n+1$

$r_i = (a+b)^ia(a+b)^{2(n-i-1)}a(a+b)^*+(a+b)^ib(a+b)^{2(n-i-1)}b(a+b)^*$ , para ; $1\le i \le n$
$s_i = (a+b)^*a(a+b)^{2(n-i-1)}a(a+b)^i+(a+b)^*b(a+b)^{2(n-i-1)}b(a+b)^i$ , para ; $1\le i \le n$
$\ell = (a+b)^{3n}$

El número total de símbolos alfabéticos en esta intersección de expresiones está en . $k$ $O(n^2)$

Usando un argumento dado en la prueba del Teorema 13 en ( 1 ), uno puede probar que cada CFG acíclico que genera debe tener al menos distintas variables, si el lado derecho de cada regla tiene longitud como máximo . La última condición es necesaria para discutir sobre el número de variables, ya que podemos generar un lenguaje finito con una sola variable. Pero desde la perspectiva del tamaño de la gramática, esta condición no es realmente una restricción, ya que podemos transformar un CFG en esta forma con solo un aumento lineal de tamaño, ver ( 2 ). Observe que el lenguaje utilizado por Arvind et al. está sobre un alfabeto de tamaño , y esto produce un límite de $L_n$ $2^n/(2n) = 2^{\Omega(\sqrt{k}/\log k)}$ $2$ $n$ $n^n/(2n)$ ; pero el argumento continúa con modificaciones obvias.

Aún así, queda una gran brecha entre y el límite inferior mencionado anteriormente. $O(4^n)$

Referencias

V. Arvind, Pushkar S. Joglekar, Srikanth Srinivasan. Circuitos aritméticos y el producto Hadamard de polinomios , FSTTCS 2009, vol. 4 de LIPIcs, págs. 25-36
Lange, Martin; Leiß, Hans (2009). "¿ A CNF o no a CNF? Una versión eficiente pero presentable del algoritmo CYK ". Informatica Didactica 8.

Hermann Gruber
fuente