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

11

J'ai la langue suivante

{0i1j2k0ijk}

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 2 s). Il pourrait pomper les v et x 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?uvwxy2vx

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
@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:

7

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 w = 0 p 1 p 2 p qui est dans la langue, et vous "marquez" tous les 0. Alors toute factorisation w = u x y z v doit être telle qu'il y ait un 0 dans x ou z . Vous pouvez également supposer que x = a k et z = b m puisque x x et z zp>0w=0p1p2pw=uxyzv0xzx=akz=bmxxzz doivent être des sous-chaînes de votre langue.

  1. Si alors w = u x 2 y z 2 v a plus de 0 que de 1z=0...0w=ux2yz2v

  2. Si et z = 1..1 alors w = u x 2 y z 2 v a plus de 1 que de 2.x=0..0z=1..1w=ux2yz2v

  3. Si et z = 2..2 alors w = u x 2 y z 2 v a plus de 0 que de 1.x=0..0z=2..2w=ux2yz2v

ux2yz2v

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
1
0p1p2p
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
5

z=uvwxyuvnwxnyn=0

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

  1. p
  2. sp
  3. s=uvxyz|vxy|p|vy|1
  4. n0
  5. uvnxynzLL

n

s=uvxyzvxyvxyvxyvyn=0uvnxynz=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