Est-ce que {

30

La langue est-elle { } hors contexte ou non?aibjck | ij,ik,jk

J'ai réalisé que j'ai rencontré presque toutes les variantes de cette question avec des conditions différentes sur la relation entre i, j et k, mais pas celle-ci.

Je suppose que ce n'est pas sans contexte, mais avez-vous une preuve?

Cem Say
la source
11
@Sariel: J'espère que ce n'est pas un problème de devoirs, car je ne sais pas comment le résoudre.
Tsuyoshi Ito
3
Cela ressemble à un problème de devoirs, car certaines des autres variantes que je mentionne sont suffisamment faciles pour être des problèmes de devoirs. Mais cette variante n'est pas un problème de devoirs. Je serais heureux si quelqu'un pouvait me donner un lien vers n'importe quel site de cours où ce problème particulier avait été assigné comme devoir.
Cem Say
2
Pouvez-vous expliquer pourquoi les techniques standard ne fonctionnent pas?
Warren Schudy
3
@Tsuyoshi ... Yeh. Vous avez raison. C'est plus difficile qu'il n'y paraît.
Sariel Har-Peled
3
Curieusement, ce langage (et l'utilisation du lemme d'Ogden) peut être trouvé dans l'exemple 6.3 (p. 130) dans la version classique de Hopcroft et «Introduction à la théorie des automates, aux langages et au calcul» d'Ullman.
Dominik D. Freydenberger

Réponses:

28

Le lemme d'Ogden devrait fonctionner:

Pour un donné, choisissez a i b p c k et marquez tous les b (et rien d'autre).paibpckb

et k sont choisis de telle sorte que pour chaque choix du nombre de b réellement pompés, il y ait un exposant de pompage tel que le nombre de b soit égal à i et un où il est égal à k .ikbbik

C'est-à-dire que et k doivent provenir de l'ensemble 1 n p { p - n + m n m N 0 } .ik1np{pn+mnmN0}

Je suis bien sûr mais trop paresseux pour prouver formellement que cet ensemble est infini.

Frank Weinberg
la source
5
En supposant que IN_0 signifie l'ensemble des entiers non négatifs, l'ensemble mentionné est infini car il contient p + im pour i = 0, 1, 2,…, où m est le plus petit commun multiple de {1,…, p}.
Tsuyoshi Ito
11
Ceux qui ne connaissaient pas le lemme d'Ogden (comme moi) peuvent trouver Wikipedia utile.
Tsuyoshi Ito
2
@Tsuyoshi: Oui, vous avez raison. Je n'ai pas vu cette simple représentation hier soir.
Frank Weinberg du
1
Cette réponse figure sur le blog de la communauté .
Aaron Sterling
Une preuve similaire est présentée dans cette réponse sur cs.se.
Hsien-Chih Chang 張顯 之
-4

Si la relation entre les trois restrictions est "OU", alors la langue est CFL. La solution utilise le fait que les LFC sont fermées sous l'union. De toute évidence, les CFL sont les suivants: , L 2 = { a i b j c ki k , j 0 } , L 3 = { a i bL1={aibjckij, k0}L2={aibjckik, j0} (si l'on n'est pas convaincu, on peut considérer L i comme une concaténation de CFL et du langage régulier. Par exemple, L 1 est { a i b ji j } concaténé à { c } .L3={aibjckjk, i0}LiL1{aibjij}{c}

La langue souhaitée est l'union de ci-dessus . C'est donc CFL.L=L1L2L3

R_G
la source
5
C'est faux. Par exemple, et donc dans votre L , mais a a b c c { a i b j c k | i j , i k , j k } . aabccL1Laabcc{aibjck | ij,ik,jk}
Dave Clarke
4
Vous supposez que »la relation entre les trois restrictions est« OU »«, mais ce n'est pas le sens voulu. Toutes les restrictions doivent être respectées (cf. le contre-exemple de Dave Clarke), puis le langage n'est pas dépourvu de contexte (cf. la réponse ci-dessus).
DaniCL