Exemple d'un langage sans contexte qui peut néanmoins être pompé?

Donc, fondamentalement, L satisfait aux conditions du lemme de pompage pour les CFL mais n'est pas un CFL (ce qui est possible selon la définition du lemme).

formal-languages context-free pumping-lemma user2329564
la source

Est-ce une question de devoirs, ou êtes-vous simplement curieux?

Yuval Filmus

Ce n'est pas un devoir mais je m'attends à le voir à l'examen (juste une intuition, connaissant mon professeur). Et je suis toujours curieux :)

user2329564

Nous avions une question similaire, mais pour les langues régulières . Le même type de construction s'applique: prenez un symbole spécial et considérez pour un langage méchant .

$

$\$$

$ K \cup {$^{k} ∣ k \neq 1} {a, b}^{*}

$\$K \cup \{ \$^k \mid k \neq 1\}\{a,b\}^*$

K \subseteq {a, b}^{*}

$K\subseteq \{a,b\}^*$

Hendrik Jan

Réponses:

L'exemple classique est . Wise montre dans son article Un fort lemme de pompage pour les langues sans contexte que ni le lemme de pompage de Bar-Hillel ni le théorème de Parikh (affirmant que l'ensemble des longueurs de mots dans un langage sans contexte est semi-linéaire) ne peuvent être utilisés pour prouver que n'est pas sans contexte. D'autres astuces comme l'intersection avec une langue régulière n'aident pas non plus. (Le lemme d'Ogden, une généralisation du lemme de pompage de Bar-Hillel, prouve que n'est pas dépourvu de contexte.) Il fournit également un lemme de pompage alternatif qui est équivalent à l'absence de contexte (pour les langages calculables), et l'utilise pour prouver que n'est pas sans contexte. $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$ $L$ $L$ $L$

Le lemme de pompage de Wise déclare qu'un langage est sans contexte si et seulement s'il y a une grammaire (non restreinte) générant et un entier tel que chaque fois que génère une "forme sententielle" (donc peut inclure des non-terminaux) de longueur , on peut écrire où sont pas vides, , et il y a un non-terminal de telle sorte que génère et génère à la fois et . $L$ $G$ $L$ $k$ $G$ $s$ $s$ $|s| > k$ $s = uvxyz$ $x,vy$ $|vxy| \leq k$ $A$ $G$ $uAz$ $A$ $vAy$ $x$

En appliquant à plusieurs reprises la condition dans le lemme, Wise est en mesure de prouver que n'est pas sans contexte, mais les détails sont quelque peu compliqués. Il donne également une condition équivalente encore plus compliquée et l'utilise pour prouver que le langage ne peut pas être écrit comme une intersection finie de langages sans contexte. $L$ $\{ a^n b a^{nm} : n,m > 0 \}$

Si vous ne pouvez pas accéder au document de Wise (il est derrière un mur payant), il existe une version dactylographiée qui est sortie sous forme de rapport technique de l'université de l'Indiana.

Un langage non contextuel qui satisfait la condition de pompage du lemme d'Ogden est donné par Johnsonbaugh et Miller, Converse of pumping lemmas , et y est attribué à Boasson et Horvath, On languages satisfying lemma d'Ogden . La langue en question est On peut écrire , correspondant aux deux lignes différentes. Notez que et que est régulier. Le lemme d'Ogden peut être utilisé pour prouver que

\begin{aligned} L^{'} & = ⋃_{n \geq 1} (e^{+} {une}^{+} {ré}^{+})^{n} (e^{+} b^{+} {ré}^{+})^{n} (e^{+} c^{+} {ré}^{+})^{n} \\ \cup (une + b + c + ré) Σ^{*} \cup Σ^{*} (une + b + c + e) \cup Σ^{*} (e ré + ré (une + b + c) + (une + b + c) e) Σ^{*} . \end{aligned}

$\begin{align*} L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*. \end{align*}$

L^{'} = L_{1} \cup L_{2}

$L' = L_1 \cup L_2$

L_{1} \cap L_{2} = \emptyset

$L_1 \cap L_2 = \emptyset$

L_{2}

$L_2$

L_{1}

$L_1$ n'est pas sans contexte, et donc non plus , mais il ne peut pas être utilisé directement pour montrer que n'est pas sans contexte.

L^{'}

$L'$

L^{'}

$L'$

Yuval Filmus
la source

N'est-il pas nécessaire qu'il y ait au moins une production ressemblant à ceci: A -> sententialForm1 A sententialForm2 pour que tout pompage soit possible

user2329564

Bien plus général: n'est-il pas nécessaire qu'un B non terminal fasse partie d'une forme sententielle dérivable de A telle que B-> sententialForm1.B.sententialfrom2 soit une production de G. Sinon, comment serait-il certain qu'un mot d'un une longueur arbitraire peut être pompée depuis A.

user2329564

Je ne vois pas pourquoi, nous avons une production , qui correspond au pompage. Par exemple, vous récupérez immédiatement le lemme de pompage depuis .

A \Rightarrow^{+} v A y

$A \Rightarrow^+ vAy$

S \Rightarrow^{*} u A z \Rightarrow^{*} u v^{i} A y^{i} z \Rightarrow^{*} u v^{i} x y^{i} z

$S \Rightarrow^* uAz \Rightarrow^* uv^iAy^iz \Rightarrow^* uv^ixy^iz$

Yuval Filmus

Cela ressemble à un bel ajout à notre référence .

Raphael

Une autre chose qui manque là-bas est la fermeture sous "mappings gsm inverse", voir planetmath.org/generalizedsequentialmachine . Je vais peut-être les ajouter à un moment donné.

Yuval Filmus

Encore plus simple: . Peut toujours pomper le s; l'intersection avec le régulier donne un non-CFL (et cela peut être prouvé en pompant le lemme). $\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\}$ $a$ $\mathcal{L}(a b^+ c^+ d^+)$

vonbrand
la source

Ce sera un bel ajout au troisième devoir ... muahaha

Renato Sanhueza

Je ne pense pas que ce soit juste. Si la langue commence par un seul , alors si vous essayez de pomper le vous devez tenir compte du fait qu'un doit également être dans la langue.

a

$a$

a

$a$

a^{0}

$a^0$

MCT

Pour développer le commentaire de MCT: considérons le mot ; choisissez , , . Ensuite, pour , n'est pas dans la langue, car il ne commence pas par un a, donc le lemme ne tient pas.

a b^{p} c^{p} d^{p}

$ab^pc^pd^p$

v = a

$v=a$

u = w = x = ε

$u=w=x=\varepsilon$

y = b^{p} c^{p} d^{p}

$y=b^pc^pd^p$

i = 0

$i=0$

u v^{i} w x^{i} y

$uv^iwx^iy$

potestasity

Un langage simple est . Intersectez avec pour obtenir un clairement non-CFL, mais vous pouvez toujours pomper le et mimétiser la longueur égale dans la mer de . $\{a b^n c^n d^n \colon n \ge 1\} \cup \mathcal{L}(a a^+ b^+ c^+ d^+)$ $\mathcal{L}(a b^+ c^+ d^+)$ $a$ ${}^+$

vonbrand
la source

L'exemple de Wise est (apparemment) également immunisé contre ces techniques, ou du moins prétend-il.

Yuval Filmus

@YuvalFilmus, semble-t-il. Mais mon exemple est à l'abri des professeurs doutant que vous ayez compris le document de Wise, ou voulant une preuve complète qu'il ne s'agit pas d'une LCF dans la limite de 2 heures de l'examen ;-)

vonbrand