Existe CFG de tamanho polinomial que descreve essa linguagem finita?

9

Existem permutações e tamanho polinomial (em | w | = n ) gramática livre de contexto que descreve a linguagem finita { w π 1 ( w ) π 2 ( w ) } sobre o alfabeto { 0 , 1 } ?π1,π2|w|=n{wπ1(w)π2(w)}{0,1}

ATUALIZAÇÃO: Para uma permutação , é possível. π é a reversão ou modificação relativamente pequena da reversão.ππ

jerr18
fonte
5
Também solicitado em math.stackexchange. O que ele quer dizer é: Existe uma sequência de permutações modo que os idiomas L n = { w π 1 ( w ) π 2 ( w ) : w { 0 , 1 } n } tem CFGs de tamanho polinomial? π1n,π2nSnLn={wπ1(w)π2(w):w{0,1}n}
Yuval Filmus
11
Sabemos se existe um CFG para ? L=nLn
Kaveh
4
@ Kaveh: A resposta é não, para qualquer sequência de permissões. Se o seu idioma fosse livre de contexto, ele terá um comprimento de bombeamento p . Aplique o lema de bombeamento para CFGs à sequência em L associada a w = 0 p 1 p . O lema do bombeamento para CFGs também vamos nos dizem que, se o OQ tem uma resposta positiva, então o CFG para L n deve usar pelo menos Ω ( n / log n ) variáveis, uma vez que precisamos 3 n ser menor do que o comprimento de bombeamento , para que nosso CFG para L n não aceite cadeias de comprimento > 3Lpw=0p1pLnΩ(n/logn)3nLn . Ainda não vejo como usar isso para descartar uma resposta positiva ao OQ, mas pode ser possível. >3n
Joshua Grochow 17/02/11
11
@Kaveh: (Além disso, se a seqüência de perms pode ser escolhido arbitrariamente, então seu idioma necessidade até não ser computável ... O OQ parece ser inerentemente não uniforme.)L
Joshua Grochow

Respostas:

13

Forma normal de Chomsky

Um CFG está em CNF (forma normal de Chomsky) se as únicas produções são da forma e A B C ; uma gramática pode ser trazida para a CNF apenas com explosão quadrática.AaABC

Para uma gramática no CNF, temos o bom lema da subpalavra: Se G gera uma palavra w , então para cada w , existe uma subpalavra x de w de comprimento / 2 | x | < que é gerado por algumas não-terminal de G . Prova: Desça a árvore de sintaxe (binária), sempre indo para o filho que gera a subpalavra mais longa. Se você começou com uma subpalavra de tamanho pelo menos , não pode ter ficado abaixo de / 2 .GGwwxw/2|x|<G/2

Solução

Sem perda de generalidade, podemos assumir que uma gramática para (uma língua com π 1 , π 2S n específico ) está na forma normal de Chomsky. A linguagem L n consiste nas palavras w ( x ) = x π 1 ( x ) π 2 ( x ) para todos os x { 0 , 1 } n .Lnπ1,π2SnLnw(x)=xπ1(x)π2(x)x{0,1}n

Usando o Sub-lema Lemma, para cada podemos encontrar uma substring s ( x ) de comprimento nw(x)s(x)gerado por algum símboloA(x)e ocorrendo na posiçãop(x).

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

Suponha que e A ( x ) = A ( y ) . Desde | s ( x ) | < n , a subpalavra s ( x ) não pode cruzar a parte x e a parte π 2 ( x ) de w ( x ) ; podemos assumir que é separado da parte x . Assim wp(x)=p(y)A(x)=A(y)|s(x)|<ns(x)xπ2(x)w(x)x tem a forma x α s ( x ) β . Isso implica que A ( x ) gera exatamente uma string, a saber s ( x ) . Portanto s ( x ) = s ( y ) .w(x)xαs(x)βA(x)s(x)s(x)=s(y)

Agora cruza π 1 ( y ) ou π 2 ( y ) em pelo menos n / 4 lugares e, portanto, determina pelo menos n / 4 bits de y . Portanto, no máximo 2 3 n / 4 strings y { 0 , 1 } n podem ter p ( x ) = p ( y )s(y)π1(y)π2(y)n/4n/4y23n/4y{0,1}np(x)=p(y)e . Como existem no máximo 3 n possibilidades para p ( y ) , obtemos que existem pelo menos 2 n / 4A(x)=A(y)3np(y) diferentes terminais na gramática.

2n/43n

π1,π2S{0,1}nnn/4πi(y)23n/4y

Mais exemplos

N0N1

Gostaria de receber uma referência para este método de prova.

Yuval Filmus
fonte
2
Yuval, você também pode copiar a solução aqui.
Kaveh
Obrigado Yuval. Se o seu método for correto e novo, eu ficaria feliz em ler um artigo investigando casos mais gerais com resultados positivos ou negativos em polisizar CFGs para idiomas finitos ou infinitos.
jerr18
3
Existe este artigo: cs.toronto.edu/~yuvalf/cfg.pdf .
Yuval Filmus
N1Σ|Σ|
11
Consulte a pergunta relacionada cstheory.stackexchange.com/q/5014, em que o Yuval postou uma resposta com uma referência publicada.
András Salamon 29/07