Je ne suis pas sûr de comprendre la question. Le nombre d'état du déterminisé peut être exponentiel par rapport au nombre d'état de l'automate de départ. On peut facilement construire un automate non déterministe avec n états, qui en enlevant une seule transition serait déterministe, et dont l'automate minimal a 2**(n-1) états. Donc une seule transition "en trop" par rapport à un déterministe peut provoquer une explosion lors de la déterminisation.
@@informatiquetheorique9146 En fait dans votre exemple, Mon raisonnement est la suivante Il y a 3 états. Et on fait des combinaisons de tout les états donc il y a 2^3 nouveaux états=8 donc ma question est est ce qu'on peut généraliser ce raisonnement à tout les automates non déterministes à Q états tel que le nombre des nouveaux état=2^Q . Ou bien votre exemple est un cas particulier ? Merci d'avance.
@@hadjuse2.87 Ça dépend... de quel algo on applique. Si on construit tout le déterminisé, arlos par construction il y a 2**n états. Mais en général, on se contente de construire que les états accessibles, et là il peu y en avoir beaucoup moins, même moins que n.
est-ce que ça marche si : on crée un nouvel état contenant toutes les entrées de l'automate, et à partir de ce nouvel état, on crée tous les autres états. Si on suit l'exemple de l'automate de la vidéo. On remarque qu'en partant de l'état {1,3}, un nouvel état {1,2} est créé grâce à "a" et un nouvel état {2} grâce à b. Et on suit la même logique jusqu'à ce qu'on n'ait plus besoin de créer de nouveaux états
Oui. je le dis (très rapidement et laconiquement en fin de vidéo). On peut se contenter, pour avoir le même langage reconnu avec un automate déterministe, de ne construire que les états accessibles. En pratique, on observe que c'est souvent sensiblement plus rapide (parfois beaucoup plus) que de tout construire. Je donne dans la vidéo la définition générale du "déterminisé".
L'état {1} est final dans le déterminisé comme on peut le voir par exemple à 4:21, il est entouré doublement. En revanche {3} ne l'est pas dans le déterminisé car 3 n'est pas final dans l'automate de départ.
Bonjour. Les vidéos sont prévues pour être des zoom sur des points (techniques souvent) du cours, et non pour former en soit un cours complet (même si on n'est pas loin). Prenez n'importe quel poly de théorie des automates finis type licence ou prépa, dans l'ordre, et cela vous donnera un ordre possible pour les vidéos.
Merci pour vos explications
merci beaucoup monsieur
😀
Concernant la génération des nouveaux états, Le 2**Q est général ou ne concerne que les états non deterministes ?
Je ne suis pas sûr de comprendre la question. Le nombre d'état du déterminisé peut être exponentiel par rapport au nombre d'état de l'automate de départ.
On peut facilement construire un automate non déterministe avec n états, qui en enlevant une seule transition serait déterministe, et dont l'automate minimal a 2**(n-1) états. Donc une seule transition "en trop" par rapport à un déterministe peut provoquer une explosion lors de la déterminisation.
@@informatiquetheorique9146
En fait dans votre exemple,
Mon raisonnement est la suivante
Il y a 3 états. Et on fait des combinaisons de tout les états donc il y a 2^3 nouveaux états=8 donc ma question est est ce qu'on peut généraliser ce raisonnement à tout les automates non déterministes à Q états tel que le nombre des nouveaux état=2^Q . Ou bien votre exemple est un cas particulier ?
Merci d'avance.
@@hadjuse2.87 Ça dépend... de quel algo on applique. Si on construit tout le déterminisé, arlos par construction il y a 2**n états. Mais en général, on se contente de construire que les états accessibles, et là il peu y en avoir beaucoup moins, même moins que n.
Merci
est-ce que ça marche si : on crée un nouvel état contenant toutes les entrées de l'automate, et à partir de ce nouvel état, on crée tous les autres états. Si on suit l'exemple de l'automate de la vidéo. On remarque qu'en partant de l'état {1,3}, un nouvel état {1,2} est créé grâce à "a" et un nouvel état {2} grâce à b. Et on suit la même logique jusqu'à ce qu'on n'ait plus besoin de créer de nouveaux états
Oui. je le dis (très rapidement et laconiquement en fin de vidéo). On peut se contenter, pour avoir le même langage reconnu avec un automate déterministe, de ne construire que les états accessibles. En pratique, on observe que c'est souvent sensiblement plus rapide (parfois beaucoup plus) que de tout construire. Je donne dans la vidéo la définition générale du "déterminisé".
mais pourquoi l'ensemble {1} {3} ne sont t-ils pas finaux ?
L'état {1} est final dans le déterminisé comme on peut le voir par exemple à 4:21, il est entouré doublement. En revanche {3} ne l'est pas dans le déterminisé car 3 n'est pas final dans l'automate de départ.
Ça
Veuillez nous donner l'ordre des vidéos
Bonjour. Les vidéos sont prévues pour être des zoom sur des points (techniques souvent) du cours, et non pour former en soit un cours complet (même si on n'est pas loin). Prenez n'importe quel poly de théorie des automates finis type licence ou prépa, dans l'ordre, et cela vous donnera un ordre possible pour les vidéos.
Merci
Les vidios de RDP