Merci beaucoup ! Cependant, il y'a une condition sur le lemme de l'étoile que je ne vois pas ici : on dit que la longueur de xy doit etre inférieure ou egale à N. Et si on la tenait en considération, les cas 2 et 3 ne satisferaient plus cette condition et donc on pourrait juste se limiter au cas 1 pour prouver que a^nb^n n'est pas rationnel !
Il y a plusieurs variantes du lemme de l'étoile (dans les faits on pompe une boucle dans l'automate). Avec la condition que la longueur "xy" de longueur inférieure ou égale à 1, cela simplifie effectivement la preuve pour a^nb^n. Il faut alors modifier un peu la preuve du lemme pour dire que les deux états égaux dans le chemin le sont au début. Ça n'est pas bien plus compliqué, mais je souhaitais rester sur quelque chose le plus intuitif possible, en se rappelant le dessin, on peut utiliser le lemme. Plutôt que la formulation en logique du premier ordre qui parfois est un peu abscons pour les étudiants. Une fois qu'on a compris, on peut voir facilement que la condition sur xy peut s'ajouter. Ou sur yz d'ailleurs. C'était un choix pédagogique.
Bonjour, à 8:05 le cas 3. J'ai une petite question. u = xyz = a...ak^kb^m b.....b Ensuite vous ecrivez que a^N b^m a^k b^N n'appartient pas à L. Mais ne faut-il pas plutôt marquer a^N a^k b^m b^N ? Pourquoi ont-ils été intervertis ?
Le mot u commence par N lettres a, N-k sont en rouge sur le slide. Suivis de N b, dont N-m sont en vert sur le slide. Le mot u est donc a^{N-k}a^kb^mb^{N-m}. C'est la partie a^kb^m qu'in va répéter avec le lemme de l'étoile. On obtient donc le mot a^{N-k}a^kb^ma^kb^mb^{N-m} qui est bien le mot a^Nb^ma^kb^N comme indiqué. J'espère que c'est plus clair.
@@informatiquetheorique9146 Ok ok merci pour votre réponse. Mais du coup en revoyant la vidéo est-ce que le cas 3 écrit comme tel ne porte pas un peu à confusion comparé à votre explication écrite ? En tout cas merci pour votre boulot :)
@@adrii1612 tu as a^(n-k) * a^k*b^m*a^k*b^m*b(N-m) . mathématiquement pour obtenir le produit de deux nombres identiques avec exposants, tu dois additionner leurs exposants... donc quand tu fais a^(n-k)*a^k...ca fait a^n et c'est pour ça qu'il y a "une inversion" visuellement...je ne sais pas si tu me suis ;-)
Et si le nombre d'états est strictement supérieur au nombre de transitions ? Le lemme de l'étoile n'est plus applicable ? Dans ce cas là, comment faire ? Pour un petit nombre d'état, on peut simplement énumérer les différents mots mais si le nombre d'état est grand, que faire ? Merci pour l'enseignement
Bonjour. Je ne crois pas. Comme montré, y est l'étiquette d'une boucle dans un chemin acceptant. On peut très bien ne pas prendre la boucle. Dans ce cas k=0.
Votre travail est d’une grande clarté sans pour autant être évasif sur les sujets abordés. Bravo !
Merci beaucoup
Travail incroyable, j’adore ! Un abonné en plus et un préparationnaire content en plus !
😀😀😀
Vous venez de me sauver la vie merci
Je suis un héros 🤣
Merci beaucoup ! J'ai enfin compris le lemme de l'étoile !
Merci infiniment pour vos vidéos tout a été très clair
Merci pour les encouragements
Bonjour, j'apprécie votre cours (du Canada!).
Merci bien (de France)
Merci monsieur pour les services
Merci beaucoup !
Cependant, il y'a une condition sur le lemme de l'étoile que je ne vois pas ici : on dit que la longueur de xy doit etre inférieure ou egale à N. Et si on la tenait en considération, les cas 2 et 3 ne satisferaient plus cette condition et donc on pourrait juste se limiter au cas 1 pour prouver que a^nb^n n'est pas rationnel !
Il y a plusieurs variantes du lemme de l'étoile (dans les faits on pompe une boucle dans l'automate). Avec la condition que la longueur "xy" de longueur inférieure ou égale à 1, cela simplifie effectivement la preuve pour a^nb^n. Il faut alors modifier un peu la preuve du lemme pour dire que les deux états égaux dans le chemin le sont au début. Ça n'est pas bien plus compliqué, mais je souhaitais rester sur quelque chose le plus intuitif possible, en se rappelant le dessin, on peut utiliser le lemme. Plutôt que la formulation en logique du premier ordre qui parfois est un peu abscons pour les étudiants. Une fois qu'on a compris, on peut voir facilement que la condition sur xy peut s'ajouter. Ou sur yz d'ailleurs. C'était un choix pédagogique.
@@informatiquetheorique9146 Merci pour la pédagogie et bonne continuation !
Bravo une super explication 👏
Merci beaucoup 😊
Bonjour, à 8:05 le cas 3. J'ai une petite question.
u = xyz = a...ak^kb^m b.....b
Ensuite vous ecrivez que a^N b^m a^k b^N n'appartient pas à L. Mais ne faut-il pas plutôt marquer a^N a^k b^m b^N ? Pourquoi ont-ils été intervertis ?
Le mot u commence par N lettres a, N-k sont en rouge sur le slide. Suivis de N b, dont N-m sont en vert sur le slide. Le mot u est donc a^{N-k}a^kb^mb^{N-m}. C'est la partie a^kb^m qu'in va répéter avec le lemme de l'étoile. On obtient donc le mot a^{N-k}a^kb^ma^kb^mb^{N-m} qui est bien le mot a^Nb^ma^kb^N comme indiqué. J'espère que c'est plus clair.
@@informatiquetheorique9146 Ok ok merci pour votre réponse. Mais du coup en revoyant la vidéo est-ce que le cas 3 écrit comme tel ne porte pas un peu à confusion comparé à votre explication écrite ?
En tout cas merci pour votre boulot :)
@@adrii1612 tu as a^(n-k) * a^k*b^m*a^k*b^m*b(N-m) . mathématiquement pour obtenir le produit de deux nombres identiques avec exposants, tu dois additionner leurs exposants... donc quand tu fais a^(n-k)*a^k...ca fait a^n et c'est pour ça qu'il y a "une inversion" visuellement...je ne sais pas si tu me suis ;-)
Mais sinon je vois qu'on est sur la même video...probablement pour le même cours :p
Merci beaucoup!
Et si le nombre d'états est strictement supérieur au nombre de transitions ? Le lemme de l'étoile n'est plus applicable ? Dans ce cas là, comment faire ? Pour un petit nombre d'état, on peut simplement énumérer les différents mots mais si le nombre d'état est grand, que faire ? Merci pour l'enseignement
Si c'est encore applicable. Je ne vois pas le problème dans le raisonnement.
vous vous êtes compliqué la vie nan ? en réalité, la condition xy
Force à toi frérot j'ai mon partiel demain aussi
🤣🤣🤣🤣🤣🤣🤣🤣🤣
What about l'algorithme de lemme minty??
Je ne vois pas le rapport entre le lemme de Minty et le lemme de l'étoile ?
Merci !
Bonjour, le lemme comporte peut être une erreur ? Le k doit être strictement supérieure à 0 (de y^k)?
Bonjour. Je ne crois pas. Comme montré, y est l'étiquette d'une boucle dans un chemin acceptant. On peut très bien ne pas prendre la boucle. Dans ce cas k=0.
@@informatiquetheorique9146 Ah je vois, ça marche mercii
@@informatiquetheorique9146 Si on ne prend pas de boucle y = epsilon non ?
@@JComprendsAuxMaths Non, il faut une boucle, donc y diffrent de epsion. En revanche y^0 (k=0) vaut epsilon.
@@informatiquetheorique9146 Ah merci j'ai saisi la nuance !
et si n est
Je ne comprends pas la question...
dans le cas de L = {a^n b^n | n
@@StarZ510 salut, non la demonstration que tu proposes emploie le lemme de l’étoile de manière erronée.