Est la langue

8

Est la langue L={0n1mn and m are co-prime} sans contexte?

Je suppose que ce n'est pas sans contexte car il semble trop compliqué pour un PDA de décider si 2 nombres sont co-amorcés ou non.

J'ai essayé d'utiliser le lemme de pompage en vain.

Toute aide serait grandement appréciée.

Éditer:

Voici l'une de mes tentatives infructueuses avec le lemme de pompage:

Laisser Nêtre une constante. Prenez une primep tel que p>N! puis prenez le mot z=0p1p+N!L. Laisserz=uvwxy être une décomposition de z satisfaisant aux conditions du lemme de pompage.

Si vx ne contient alors que des zéros |vx|=k est un entier entre 1 et N. Définirm comme m=N!/k. Pouri=m+1 le mot uviwxiy=0p+N!1p+N!L

Cependant, je n'ai pas réussi à trouver un tel entier i pour les autres cas de décomposition.

Robert777
la source
1
Bienvenue en informatique ! Permettez-moi de vous orienter vers nos questions de référence qui pourraient couvrir votre problème. Veuillez résoudre les questions connexes répertoriées ici, essayez de résoudre à nouveau votre problème et modifiez-le pour inclure vos tentatives ainsi que les problèmes spécifiques que vous avez rencontrés. Je pense que le théorème de Parikh pourrait fonctionner pour vous.
Raphael
2
Parikh devrait fonctionner, mais aussi le pompage standard / Ogden, non?
Ran G.
C'est en fait une question de quiz. Puisque nous n'avons pas appris le théorème de Parikh, il existe probablement un moyen de montrer qu'il n'est pas dépourvu de contexte avec le lemme de pompage ou avec les propriétés de fermeture.
Robert777
@Raphael, dans ce cas, le théorème de Parikh n'ajoute vraiment rien au-delà du lemme de pompage direct (c'est-à-dire de 0n1m peut obtenir tout 0n+ka1m+kb pour certains a, b pas à la fois zéro et k1). Mais je ne vois aucun moyen de forcergcd(n+ka,m+kb)1.
vonbrand
@vonbrand Nous pouvons travailler sur place; voir ici . L¯L(01)
Raphael

Réponses:

4

Ridicule que je ne l'ai pas vu plus tôt ...

La preuve que le langage (appelez-le ) n'est pas sans contexte est par contradiction. Supposons que est sans contexte, par le lemme de pompage pour les CFG, il y a une constante telle que chaque chaîne telle que elle puisse être écrite avec tel que pour tout la chaîne . Prenez nombres premiers différents (tels que ) et , et prenez . La chaîne pompée seraLLNσL|σ|Nσ=uvxyzvyϵk0uvkxykzLm,ngcd(m,n)=1m,n>2Nσ=0m1n0m+ka1n+kb pour certaines constantes , , pas toutes les deux nulles, et telles que et (nous avons par la façon dont , ont été sélectionnés). Le cas de l'un d'eux zéro était couvert par OP, alors considérons . Maintenant:aba<mb<na,bN<m/2,n/2mna,b0

m+ka0(modn)n+kb0(modm)

Ceci a une solution unique modulo par le théorème du reste chinois (nous avons , et comme est premier, ; de même et ), et ainsi nous pouvons écrire: c'est-à-dire . Contradiction.kmna<nngcd(a,n)=1bm

m+ka0(modmn)n+kb0(modmn)
mngcd(m+ka,n+kb)
vonbrand
la source
Merci pour votre réponse. J'ai aimé la façon dont vous avez abordé cela. Cependant, je ne comprends pas comment avez-vous utilisé le théorème du reste chinois si cela ne peut être appliqué que sur un système de congruences linéaires de la forme:
xb1(modm1)xb2(modm2)
Robert777
@ Robert777, écrivez juste et ainsi de suite. kam(modn)
vonbrand
1
mais vous obtenez une congruence de la forme: et ce n'est pas la même chose. Par exemple, si alors la congruence n'a pas de solutions.
axb(modm)
gcd(a,m)|b
Robert777
1
@ Robert777, vous avez absolument raison. Changé pour sélectionner , premier. Merci! mn
vonbrand
Bon, après avoir utilisé le théorème du reste chinois, pourquoi pouvons-nous écrire ces congruences:
m+ka0(modmn)n+kb0(modmn)
Robert777