Comment puis-je prouver que cette langue n'est pas sans contexte?

J'ai la langue suivante

$\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$

J'essaie de déterminer dans quelle classe de langue Chomsky il s'intègre. Je peux voir comment cela pourrait être fait en utilisant une grammaire contextuelle, donc je sais qu'elle est au moins contextuelle. Il semble que ce ne serait pas possible de faire avec une grammaire sans contexte, mais j'ai du mal à le prouver.

Il semble passer le lemme de pompage à la fourche parce que si est tout placé dans la troisième partie d'un mot (la section avec tous les s). Il pourrait pomper les et autant de fois que vous le souhaitez et resterait dans la langue. Si je me trompe, pourriez-vous me dire pourquoi, si j'ai raison, je pense toujours que ce langage n'est pas sans contexte, alors comment pourrais-je le prouver? $uvwxy$ $2$ $v$ $x$

formal-languages context-free formal-grammars pumping-lemma justausr
la source

Je ne sais pas comment en faire une preuve formelle, mais s'assurer que i <= j <= k nécessite un contexte (la valeur de la variable précédente).

Kevin

doublon possible de Comment prouver qu'une langue n'est pas sans contexte?

Raphael

@Raphael, j'ai lu ce post avant celui-ci et je ne savais pas comment l'appliquer à mon exemple à cause de son caractère abstrait. Avec la relation de chaque caractère étant> = le nombre de caractères précédents, je ne voyais pas comment diviser l'xyzv en mot pour utiliser le lemme d'Ogden. BlueMagister et jmad ont développé l'autre article pour que mon exemple soit clair.

justausr

@Raphael Je ne suis pas d'accord pour dire qu'il s'agit d'une application triviale du cas général. Il n'est pas si facile de choisir la méthode à utiliser et l'exemple à appliquer.

Gilles 'SO- arrête d'être méchant'

Réponses:

Vous pouvez forcer le pompage à certains endroits, en utilisant le lemme d'Ogden , par exemple en marquant tous les 0.

Supposons qu'il soit sans contexte, alors le lemme d'Ogden vous donne un , vous lui donnez qui est dans la langue, et vous "marquez" tous les 0. Alors toute factorisation doit être telle qu'il y ait un dans ou . Vous pouvez également supposer que et puisque et $p>0$ $w=0^p1^p2^p$ $w=uxyzv$ $0$ $x$ $z$ $x=a^k$ $z=b^m$ $xx$ $zz$ doivent être des sous-chaînes de votre langue.

Si alors a plus de 0 que de 1 $z=0...0$ $w=ux^2yz^2v$
Si et alors a plus de 1 que de 2. $x=0..0$ $z=1..1$ $w=ux^2yz^2v$
Si et alors a plus de 0 que de 1. $x=0..0$ $z=2..2$ $w=ux^2yz^2v$

$ux^2yz^2v$

Pour d'autres techniques, voir la discussion: Comment prouver qu'une langue n'est pas sans contexte?

jmad
la source

Est-ce pour la même langue que moi? Cela semble être pour le langage similaire où tous les 0, les 1 et les 2 sont de longueur égale. Cette langue a le nombre de 2> = le nombre de 1> = le nombre de 0

justausr

0^{p} 1^{p} 2^{p}

$0^p1^p2^p$

Gotcha, je n'ai jamais entendu parler du lemme d'ogden, donc je vais devoir y réfléchir. Ai-je raison de dire qu'il échoue au lemme de pompage?

justausr

@justausr non plus, jusqu'à récemment (et grâce à la discussion à laquelle j'ai fait référence). Et oui, vous aviez raison: le lemme de pompage fait presque la même chose mais ne pas choisir où pomper le rend inutile ici.

jmad

$z = uvwxy$ $uv^nwx^ny$ $n = 0$

EDIT: Comme le déclare Jmad , le lemme de pompage est comme un jeu:

$p$

$s$ $p$

$s=uvxyz$ $|vxy|≤p$ $|vy|≥1$

$n≥0$

$uv^nxy^nz$ $L$ $L$

$n$

$s=uvxyz$ $vxy$ $vxy$ $vxy$ $v$ $y$ $n=0$ $uv^nxy^nz = uxz$

Blue Magister
la source

Voulez-vous dire mettre tout uvwxy dans la section avec 2?

justausr

Si on lui donne le bon mot. Je développerai ma réponse.

Blue Magister

Ici, essayez-le maintenant. Je ne sais pas si mon lemme de pompage est le même que votre lemme de pompage, donc j'en appelle à Wikipedia .

Blue Magister