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 } ?
ATUALIZAÇÃO: Para uma permutação , é possível. π é a reversão ou modificação relativamente pequena da reversão.
Respostas:
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.A→a A→BC
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 .G G w ℓ≤w x w ℓ/2≤|x|<ℓ G ℓ ℓ/2
Solução
Sem perda de generalidade, podemos assumir que uma gramática para (uma língua com π 1 , π 2 ∈ S 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,π2∈Sn Ln w(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).
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)|<n s(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/4 n/4 y 23n/4 y∈{0,1}n p(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) 3n p(y) diferentes terminais na gramática.
Mais exemplos
Gostaria de receber uma referência para este método de prova.
fonte