La preuve que

8

Montre CA L={an2|n0} n'est pas régulier

Salut les gars. Je prends un cours de CS et ce truc est vraiment nouveau pour moi, alors soyez indulgent avec moi. J'ai essayé de voir si j'obtenais une contradiction en utilisant le lemme de pompage pour les langues régulières et j'ai travaillé comme ceci:

Supposer Lest régulier. Ensuite, il doit y avoir un nombre naturelm pour tous les mots z dans L avec longueur |z|m et il existe une décomposition z=uvw,|uv|m,|v|>0, pour que u(vi)w est dans la langue de tout i0.

Considérez la chaîne am2.

alors uv=ak2=ax+y, pour certains km et x=(k1)2.
alorsv=ay=a2k1.

Laisser i=2. alorsu(v2)w=ax+2y. Maisx+2yn'est pas nécessairement un nombre naturel -> Contradiction! Par conséquent,L ne peut pas être régulier.

Eh bien, je sais que ce chemin est inutilement compliqué et vous pouvez le prouver différemment (je connais déjà la solution la plus simple). Mais ma question est la suivante: ma preuve est-elle également valable ou contient-elle un défaut? Est-ce formellement correct?

J'apprécie tout commentaire! Merci!

Gilles 'SO- arrête d'être méchant'
la source
1
FYI - Les expressions régulières telles que définies en informatique théorique et les expressions régulières utilisées par les programmeurs sont liées, mais très différentes.
2
Vous semblez avoir commis certaines des erreurs classiques lors de l'application du lemme de pompage. Veuillez noter notre question de référence pour une explication détaillée et un exemple.
Raphael
Ce n'est pas correct, non. Votre argument ne peut pas dépendre de l'hypothèseuv=ak2.
Patrick87

Réponses:

8

Vous ne pouvez pas en déduire uv=ak2, tout ce que le lemme de pompage vous donne, c'est que |uv|m. Tous les nombres ne sont pas inférieurs àmsont des carrés. Non seulement cela, mais même en supposant queuv=ak2, il n'y a aucune raison de supposer que v=a2k1; tout le lemme de pompage vous donne est quevn'est pas vide. Enfin, pour obtenir une contradiction, il ne suffit pas quex+2y pas besoin d' être un carré, ça ne doit pas être un carré! Depuisx et x+y sont des carrés adjacents, il est en fait vrai que x+2y n'est pas un carré.

Yuval Filmus
la source
Des conseils sur la façon de réparer la preuve?
Raphael
L'OP "connaît déjà la solution la plus simple", ce qui, je suppose, revient à la preuve fixe.
Yuval Filmus
@YuvalFilmus Pas nécessairement. Il existe une preuve assez simple en utilisant le théorème de Myhill-Nerode qui n'a rien à voir avec le lemme de pompage. C'est peut-être celui auquel le PO fait référence.
Patrick87