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

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

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

fl.formal-languages grammars context-free jerr18
la source

Également demandé sur math.stackexchange. Il veut dire: existe-t-il une suite de permutations

telles que les langues

ont des CFG de taille polynomiale?

π_{1}^{n}, π_{2}^{n} \in S_{n}

$\pi_1^n,\pi_2^n \in S_n$

L_{n} = {w π_{1} (w) π_{2} (w) : w \in {0, 1}^{n}}

$L_n = \{w \pi_1(w) \pi_2(w) : w\in \{0,1\}^n\}$

Yuval Filmus

math.stackexchange.com/questions/22361/…

Tsuyoshi Ito

Savons-nous s'il existe un CFG pour

L = ⋃_{n} L_{n}

$L = \bigcup_n L_n$

Kaveh

@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

. Appliquer le lemme de pompage des CFG à la chaîne en L associée à

. 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

doit utiliser au moins

variables, car nous avons besoin de

pour être inférieur à la longueur de pompage , de sorte que notre CFG pour

n'accepte aucune chaîne de longueur

L

$L$

p

$p$

w = 0^{p} 1^{p}

$w = 0^p 1^p$

L_{n}

$L_n$

Ω (n / \log n)

$\Omega(n / \log n)$

3 n

$3n$

L_{n}

$L_n$

. Je ne vois pas encore comment utiliser cela pour exclure une réponse positive à l'OQ, mais cela pourrait être possible.

> 3 n

$> 3n$

Joshua Grochow

@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

$L$

Joshua Grochow

Réponses:

Forme normale de Chomsky

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

Pour une grammaire en CNF, nous avons le joli sous-lemme: si génère un mot , alors pour chaque , il y a un sous-mot de de longueur qui est généré par un non-terminal de . 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 . $G$ $G$ $w$ $\ell \leq w$ $x$ $w$ $\ell/2 \leq |x| < \ell$ $G$ $\ell$ $\ell/2$

Solution

Sans perte de généralité, nous pouvons supposer qu'une grammaire pour (un tel langage avec spécifique ) est en forme normale de Chomsky. Le langage est composé des mots pour tout . $L_n$ $\pi_1,\pi_2 \in S_n$ $L_n$ $w(x) = x\pi_1(x)\pi_2(x)$ $x \in \{0,1\}^n$

$w(x)$ $s(x)$

\frac{n}{2} \leq | s (x) | < n

$\frac{n}{2} \leq |s(x)| < n$

A (x)

$A(x)$

p (x)

$p(x)$

$p(x) = p(y)$ $A(x) = A(y)$ $|s(x)|<n$ $s(x)$ $x$ $\pi_2(x)$ $w(x)$ $x$ $w(x)$ $x \alpha s(x) \beta$ $A(x)$ $s(x)$ $s(x) = s(y)$

$s(y)$ $\pi_1(y)$ $\pi_2(y)$ $n/4$ $n/4$ $y$ $2^{3n/4}$ $y \in \{0,1\}^n$ $p(x) = p(y)$ $A(x) = A(y)$ $3n$ $p(y)$

\frac{2^{n / 4}}{3 n}

$\frac{2^{n/4}}{3n}$

$\pi_1,\pi_2 \in S_{\{0,1\}^n}$ $n$ $n/4$ $\pi_i(y)$ $2^{3n/4}$ $y$

Plus d'exemples

$\mathbb{N}$ $0$ $\mathbb{N}_{\geq 1}$

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

Yuval Filmus
la source

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

Il y a ce texte: cs.toronto.edu/~yuvalf/cfg.pdf .

Yuval Filmus

N_{\geq 1}

$N_{\geq 1}$

Σ^{| Σ |}

$\Sigma^{|\Sigma|}$

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