Cette langue est-elle sans contexte?

8

Est la langue

L={a,b}{(anbn)nn1}

sans contexte? Je crois que la réponse est que ce n'est pas une LFC, mais je ne peux pas le prouver par le lemme d'Ogden ou le lemme de pompage.

Andrés Felipe Téllez Crespo
la source
Crossposted sur math.SE ; s'il vous plaît ne faites pas ça! Avez-vous vérifié la question que je vous ai indiquée? Veuillez inclure vos tentatives et pourquoi elles ont échoué.
Raphael
Le théorème de Parikh fonctionne pour mais pas pour ; malheureusement, . Même le lemme d'échange semble être rempli. Wow, méchant. {(anbn)nn1}LΨ{a,b}[L]=N2
Raphael

Réponses:

8

Allusion:

Oui

Solution:

{(anbn)nn1}={an1bn2an2k1bn2k}:k1n1=ki.ni=ni+1}


et donc le complément est qui est sans contexte car vous pouvez facilement écrire un PDA non déterministe.

{a,b}{(anbn)nn1}={an1bn2an2k1bn2k:n1ki.nini+1}


sdcvvc
la source
2
Ooohhh! * facepalm * Peut-être que vous voulez ajouter l'astuce de conception centrale; cela pourrait ne pas être évident pour le novice.
Raphael
Je ne comprends pas, je pensais que le complément d'une CFL n'était pas CFL en général. Merci
Andrés Felipe Téllez Crespo
{(anbn)n} n'est pas sans contexte, mais son complément l'est.
sdcvvc
@ AndrésFelipeTéllezCrespo: Le complément d'une CFL n'est pas toujours CFL (donc pas de propriété de fermeture) mais personne ne dit qu'il n'y a pas de CFL dont le complément est CFL. En particulier, tous les compléments de toutes les langues régulières sont sans contexte (car ils sont même réguliers).
Raphael
Des langages similaires à - une disjonction finie de conditions appropriées - peuvent être résolus en utilisant le non-déterminisme: devinez la condition violée et vérifiez qu'elle est violée (ignorez le reste). L
Raphael