Existe-t-il une taille polynomiale CFG qui décrit ce langage fini?

9

Existe-t-il des permutations et une grammaire sans contexte de taille polynomiale (dans | w | = n ) qui décrivent le langage fini { w π 1 ( w ) π 2 ( w ) } sur l'alphabet { 0 , 1 } ?π1,π2|w|=n{wπ1(w)π2(w)}{0,1}

MISE À JOUR: Pour une permutation c'est possible. π est l'inversion ou la modification relativement mineure de l'inversion.ππ

jerr18
la source
5
Également demandé sur math.stackexchange. Il veut dire: existe-t-il une suite de permutations telles que les langues L n = { w π 1 ( w ) π 2 ( w ) : w { 0 , 1 } n } ont des CFG de taille polynomiale? π1n,π2nSnLn={wπ1(w)π2(w):w{0,1}n}
Yuval Filmus
1
Savons-nous s'il existe un CFG pour ? L=nLn
Kaveh
4
@Kaveh: La réponse est non, pour toute séquence de perms. Si votre langue était hors contexte, alors elle a une longueur de pompage p . Appliquer le lemme de pompage des CFG à la chaîne en L associée à w = 0 p 1 p . Le lemme de pompage pour les CFG nous permet également de dire que si l'OQ a une réponse positive, alors le CFG pour L n doit utiliser au moins Ω ( n / log n ) variables, car nous avons besoin de 3 n pour être inférieur à la longueur de pompage , de sorte que notre CFG pour L n n'accepte aucune chaîne de longueur > 3Lpw=0p1pLnΩ(n/logn)3nLn . Je ne vois pas encore comment utiliser cela pour exclure une réponse positive à l'OQ, mais cela pourrait être possible. >3n
Joshua Grochow
1
@Kaveh: (De plus, si la séquence de perms peut être choisie arbitrairement, alors votre langue n'a même pas besoin d'être calculable ... L'OQ semble être intrinsèquement non uniforme.)L
Joshua Grochow

Réponses:

13

Forme normale de Chomsky

Un CFG est en CNF (forme normale de Chomsky) si les seules productions sont de la forme et A B C ; une grammaire peut être amenée à CNF avec seulement une explosion quadratique.AaABC

Pour une grammaire en CNF, nous avons le joli sous-lemme: si G génère un mot w , alors pour chaque w , il y a un sous-mot x de w de longueur / 2 | x | < qui est généré par un non-terminal de G . Preuve: Descendez l'arbre de syntaxe (binaire), en allant toujours vers l'enfant qui génère le sous-mot le plus long. Si vous avez commencé avec un sous-mot de taille au moins , vous ne pouvez pas être passé en dessous de / 2 .GGwwxw/2|x|<G/2

Solution

Sans perte de généralité, nous pouvons supposer qu'une grammaire pour (un tel langage avec π 1 , π 2S n spécifique ) est en forme normale de Chomsky. Le langage L n est composé des mots w ( x ) = x π 1 ( x ) π 2 ( x ) pour tout x { 0 , 1 } n .Lnπ1,π2SnLnw(x)=xπ1(x)π2(x)x{0,1}n

w(x)s(x)

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

p(x)=p(y)A(x)=A(y)|s(x)|<ns(x)xπ2(x)w(x)xw(x)xαs(x)βA(x)s(x)s(x)=s(y)

s(y)π1(y)π2(y)n/4n/4y23n/4y{0,1}np(x)=p(y)A(x)=A(y)3np(y)

2n/43n

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

Plus d'exemples

N0N1

J'apprécierais une référence pour cette méthode de preuve.

Yuval Filmus
la source
2
Yuval, pourriez-vous s'il vous plaît copier la solution ici aussi.
Kaveh
Merci Yuval. Si votre méthode est correcte et nouvelle, je serais heureux de lire un article sur des cas plus généraux avec des résultats positifs ou négatifs sur les CFG polysize pour les langues finies ou infinies.
jerr18
3
Il y a ce texte: cs.toronto.edu/~yuvalf/cfg.pdf .
Yuval Filmus
N1Σ|Σ|
1
Voir la question connexe cstheory.stackexchange.com/q/5014 où Yuval a publié une réponse avec une référence publiée.
András Salamon