Comprendre la déterminisation d'un automate fini (didacticiel)

Рет қаралды 31,016

Informatique Théorique

Күн бұрын

Пікірлер: 21

@Jino2221 2 жыл бұрын

Merci pour vos explications

@wallwall3140 Ай бұрын

Incroyable merci

@informatiquetheorique9146 Ай бұрын

Merci

@physics4925 2 жыл бұрын

merci beaucoup monsieur

@informatiquetheorique9146 2 жыл бұрын

😀

@hadjuse2.87 Жыл бұрын

Concernant la génération des nouveaux états, Le 2**Q est général ou ne concerne que les états non deterministes ?

@informatiquetheorique9146 Жыл бұрын

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.

@hadjuse2.87 Жыл бұрын

@@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.

@informatiquetheorique9146 Жыл бұрын

@@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.

@sw4ty-donut069 7 ай бұрын

mais pourquoi l'ensemble {1} {3} ne sont t-ils pas finaux ?

@informatiquetheorique9146 7 ай бұрын

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.

@raskolnikov5 9 ай бұрын

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

@informatiquetheorique9146 9 ай бұрын

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é".

@nfoxx922 4 жыл бұрын

Merci

@Mustapha309 3 жыл бұрын

Les vidios de RDP

@Nemesis64710 18 күн бұрын

faudrait filtrer le bruit sur l'audio aussi ^^

@informatiquetheorique9146 17 күн бұрын

J'ai fais mes premières vidéos pour mes étudiants, pendant le confinement COVID, car certains avaient un accès très limité au internet. J'ai fais avec les moyens du bord... Je me suis un peu mieux équipé ensuite, mais cela reste une chaîne non monétisée, regarde qui veut.

@Mustapha309 3 жыл бұрын

Veuillez nous donner l'ordre des vidéos

@informatiquetheorique9146 3 жыл бұрын

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.