¿Existe el tamaño polinómico CFG que describe este lenguaje finito?

9

¿Existen permutaciones y gramática libre de contexto de tamaño polinómico (en ) que describe el lenguaje finito sobre el alfabeto ?π1,π2|w|=n{wπ1(w)π2(w)}{0,1}

ACTUALIZACIÓN: Para una permutación es posible. es la inversión o modificación relativamente menor de la inversión.ππ

jerr18
fuente
55
También se le preguntó en math.stackexchange. Lo que quiere decir es: ¿Hay una secuencia de permutaciones π1n,π2nSn tal que los idiomas Ln={wπ1(w)π2(w):w{0,1}n} tiene CFG de tamaño polinómico?
Yuval Filmus
1
¿Sabemos si hay un CFG para ? L=nLn
Kaveh
44
@Kaveh: La respuesta es no, para cualquier secuencia de permisos. Si su lenguaje no tiene contexto, entonces tiene una longitud de bombeo p . Aplique el lema de bombeo para CFG a la cadena en L asociada a w = 0 p 1 p . El lema de bombeo para CFG también nos permite decir que, si el OQ tiene una respuesta positiva, entonces el CFG para L n debe usar al menos variables Ω ( n / log n ) , ya que necesitamos 3 n para ser menor que la longitud de bombeo , para que nuestro CFG para L n no acepte cadenas de longitud > 3Lpw=0p1pLnΩ(n/logn)3nLn . Todavía no veo cómo usar esto para descartar una respuesta positiva al OQ, pero podría ser posible. >3n
Joshua Grochow
1
@Kaveh: (Además, si la secuencia de permisos se puede elegir arbitrariamente, entonces su lenguaje ni siquiera necesita ser computable ... El OQ parece ser inherentemente no uniforme.)L
Joshua Grochow

Respuestas:

13

Forma normal Chomsky

Un CFG está en CNF (forma normal de Chomsky) si las únicas producciones son de la forma y A B C ; una gramática puede llevarse a CNF con solo una explosión cuadrática.AaABC

Para una gramática en CNF, tenemos el bonito Lema de la subword: si G genera una palabra w , entonces para cada w , hay una subword x de w de longitud / 2 | x | < que se genera por algunos no terminal de G . Prueba: descienda el árbol de sintaxis (binario), siempre yendo al hijo que genera la subpalabra más larga. Si comenzó con una palabra secundaria de tamaño de al menos , no puede haber ido por debajo de / 2 .GGwwxw/2|x|<G/2

Solución

Sin pérdida de generalidad, podemos suponer que una gramática para (tal lenguaje con π 1 , π 2S n específico ) está en forma normal de Chomsky. El lenguaje L n consiste en las palabras w ( x ) = x π 1 ( x ) π 2 ( x ) para todo x { 0 , 1 } n .Lnπ1,π2SnLnw(x)=xπ1(x)π2(x)x{0,1}n

Usando el subtítulo Lema, para cada podemos encontrar una subcadena s ( x ) de longitud nw(x)s(x)generado por algún símboloA(x)y que ocurre en la posiciónp(x).

n2|s(x)|<n
A(x)p(x)

Suponga que y A ( x ) = A ( y ) . Desde | s ( x ) | < n , la subparte s ( x ) no puede intersectar tanto la parte x como la parte π 2 ( x ) de w ( x ) ; podemos suponer que es disjunto de la parte x . Así wp(x)=p(y)A(x)=A(y)|s(x)|<ns(x)xπ2(x)w(x)x tiene la forma x α s ( x ) β . Esto implica que A ( x ) genera exactamente una cadena, es decir s ( x ) . Por lo tanto s ( x ) = s ( y ) .w(x)xαs(x)βA(x)s(x)s(x)=s(y)

Ahora cruza con π 1 ( y ) o π 2 ( y ) en al menos n / 4 lugares, y por lo tanto determina al menos n / 4 bits de y . Por lo tanto, como máximo 2 3 n / 4 cadenas y { 0 , 1 } n pueden tener p ( x ) = p ( y )s(y)π1(y)π2(y)n/4n/4y23n/4y{0,1}np(x)=p(y)y . Como hay a lo sumo 3 n posibilidades para p ( y ) , obtenemos que hay al menos 2 n / 4A(x)=A(y)3np(y) diferentes no terminales en la gramática.

2n/43n

Comentario: La misma prueba funciona si , es decir, son permutaciones arbitrarias en el conjunto de todas las palabras de n bits. Dados n / 4 bits de π i ( y ) , hay exactamente 2 3 n / 4 preimágenes y .π1,π2S{0,1}nnn/4πi(y)23n/4y

Más ejemplos

Usando el mismo método, se puede demostrar que el idioma en el que cada carácter aparece exactamente dos veces requiere CFG de tamaño exponencial en el tamaño del alfabeto. Podemos reemplazar "dos veces" con cualquier subconjunto de no sean cuatro triviales (ignorando 0 , ya sea que no contenga ninguno de N 1 o todo).N0N1

Agradecería una referencia para este método de prueba.

Yuval Filmus
fuente
2
Yuval, ¿podría copiar la solución aquí también?
Kaveh
Gracias Yuval Si su método es correcto y novedoso, me complacería leer un artículo que investigue casos más generales con resultados positivos o negativos sobre CFG polisizados para lenguajes finitos o infinitos.
jerr18
3
Hay este artículo: cs.toronto.edu/~yuvalf/cfg.pdf .
Yuval Filmus
Supongo que por la excepción te refieres a "al menos una aparición de terminal". ¿Significaría que puede generar todas las permutaciones intersectando con Σ | Σ | ? N1Σ|Σ|
jerr18
1
Consulte la pregunta relacionada cstheory.stackexchange.com/q/5014 donde Yuval publicó una respuesta con una referencia publicada.
András Salamon