{"id":10427,"date":"2020-10-30T12:28:30","date_gmt":"2020-10-30T11:28:30","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=10427"},"modified":"2024-02-13T08:39:25","modified_gmt":"2024-02-13T07:39:25","slug":"optimisation-automates","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/","title":{"rendered":"9 Corrected exercises: optimization of automata"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"10427\" class=\"elementor elementor-10427\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6c795c8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6c795c8\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-3812ed8\" data-id=\"3812ed8\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-3537680 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"3537680\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/theorie-des-langages\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Th\u00e9orie des langages<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-2a4c32d\" data-id=\"2a4c32d\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7beac4d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"7beac4d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-48ae2ae\" data-id=\"48ae2ae\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2b40dde elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2b40dde\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Langage_formel\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-fa4ffc9 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fa4ffc9\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-262c754\" data-id=\"262c754\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7325575 elementor-widget elementor-widget-heading\" data-id=\"7325575\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercices-corriges-Optimisation-des-automates-par-determinisation-et-minimisation\" >Exercices corrig\u00e9s Optimisation des automates par d\u00e9terminisation et minimisation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Determinisation\" >D\u00e9terminisation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-1\" >Exercice 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-2\" >Exercice 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-3\" >Exercice 3<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-4\" >Exercice 4<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-5\" >Exercice 5<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-6\" >Exercice 6<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Minimisation\" >Minimisation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-7\" >Exercice 7<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-8\" >Exercice 8<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/corrective-exercises-optimization-of-automata\/#Exercice-9\" >Exercice 9<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-Optimisation-des-automates-par-determinisation-et-minimisation\"><\/span>Exercices corrig\u00e9s Optimisation des automates par d\u00e9terminisation et minimisation<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b2f0482 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b2f0482\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-3fe9040\" data-id=\"3fe9040\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7673c36 elementor-widget elementor-widget-text-editor\" data-id=\"7673c36\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Vous trouverez sur cette page des exercices corrig\u00e9s sur : optimisation des automates, la d\u00e9terminisation et la minimisation.<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"97\" height=\"97\" title=\"\"><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7306c94 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7306c94\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-ea9cf38\" data-id=\"ea9cf38\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e068808 elementor-widget elementor-widget-heading\" data-id=\"e068808\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Determinisation\"><\/span>D\u00e9terminisation<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ed6bd38 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ed6bd38\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e2e9ca6\" data-id=\"e2e9ca6\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4e0e429 elementor-widget elementor-widget-heading\" data-id=\"4e0e429\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Exercice 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ad1c703 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ad1c703\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-83d8191\" data-id=\"83d8191\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b5fd33d elementor-widget elementor-widget-text-editor\" data-id=\"b5fd33d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>D\u00e9terminiser les automates suivants\u00a0:<\/p><p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-10433 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image26.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation.\" width=\"519\" height=\"269\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image26.png 519w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image26-300x155.png 300w\" sizes=\"(max-width: 519px) 100vw, 519px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-245df3d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"245df3d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-26367b9\" data-id=\"26367b9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5574c64 elementor-widget elementor-widget-toggle\" data-id=\"5574c64\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-8961\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-8961\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-8961\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-8961\"><p><img decoding=\"async\" class=\"aligncenter wp-image-10434 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image27.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"570\" height=\"556\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image27.png 570w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image27-300x293.png 300w\" sizes=\"(max-width: 570px) 100vw, 570px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e3068b4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e3068b4\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c590f65\" data-id=\"c590f65\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4ed430d elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"4ed430d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7486970 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7486970\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-151f67b\" data-id=\"151f67b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-aa1fbec elementor-widget elementor-widget-heading\" data-id=\"aa1fbec\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Exercice 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8b3fbb2 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8b3fbb2\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7362f34\" data-id=\"7362f34\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7b95284 elementor-widget elementor-widget-text-editor\" data-id=\"7b95284\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On consid\u00e8re l&rsquo;alphabet A constitu\u00e9 des lettres de l&rsquo;alphabet de la langue fran\u00e7aise et le langage L = { w \u2208\u00a0A* \/ w se termine par man}. \u00a0Trouver un automate d\u00e9terministe qui engendre L.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-68bcaa3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"68bcaa3\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d9b22ec\" data-id=\"d9b22ec\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-9151bed elementor-widget elementor-widget-toggle\" data-id=\"9151bed\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1521\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1521\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1521\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1521\"><p>Repr\u00e9sentons par x toutes les lettres qui ne sont pas {a,m,n}. L\u2019automate doit reconnaitre les mots [a-z\u00a0; A-Z]<sup>*<\/sup>man. Construisons un automate ind\u00e9terministe avec l\u2019algorithme de Thompson (ici nous remarquons que les epsilons transitions ne sont pas utiles). L\u2019automate est le suivant\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10435\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image28.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"407\" height=\"180\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image28.png 407w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image28-300x133.png 300w\" sizes=\"(max-width: 407px) 100vw, 407px\" \/><\/p><p>Apr\u00e8s d\u00e9terminisation nous obtenons l\u2019automate suivant\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10436 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image29.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"480\" height=\"481\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image29.png 480w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image29-300x300.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image29-150x150.png 150w\" sizes=\"(max-width: 480px) 100vw, 480px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3c3fa30 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3c3fa30\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7febfaa\" data-id=\"7febfaa\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ab729ed elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"ab729ed\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-40a203b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"40a203b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0745ed4\" data-id=\"0745ed4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-49094ae elementor-widget elementor-widget-heading\" data-id=\"49094ae\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Exercice 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e5158ba elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e5158ba\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c131d7c\" data-id=\"c131d7c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8b2870f elementor-widget elementor-widget-text-editor\" data-id=\"8b2870f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Soit L le langage accept\u00e9 par l\u2019automate A ci-dessous\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10437 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image30.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"296\" height=\"155\" title=\"\"><\/p><p>Trouver une grammaire r\u00e9guli\u00e8re engendrant L. \u00a0Trouver une expression r\u00e9guli\u00e8re d\u00e9notant L. Trouver un automate d\u00e9terministe acceptant L.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-56dd29a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"56dd29a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a948282\" data-id=\"a948282\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-439bf59 elementor-widget elementor-widget-toggle\" data-id=\"439bf59\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-7081\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7081\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-7081\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7081\"><p>Voici les productions de grammaire obtenues directement \u00e0 partir de l\u2019automate : P \u2192 aP, P \u2192 aQ, Q \u2192 bP, Q \u2192 R, R \u2192 bR, R \u2192 cQ, R \u2192 bP, R \u2192 epsilon. Les non-terminaux (donc les n\u0153uds de l\u2019automate) de la grammaire sont {P,Q,R}, le symbole initial est P.<\/p><p>En d\u00e9notant avec X<sub>p<\/sub>, X<sub>q<\/sub>, X<sub>r<\/sub>\u00a0les langages accept\u00e9s \u00e0 partir des \u00e9tats P, Q et R respectivement, le syst\u00e8me d\u2019\u00e9quations pour ces langages est :<\/p><p>Attention, une r\u00e9cursion d\u2019un non-terminal donnera une \u00e9toile, et une distribution avec des non-terminaux provoquera une concat\u00e9nation\u00a0!<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10438 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image31.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"412\" height=\"361\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image31.png 412w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image31-300x263.png 300w\" sizes=\"(max-width: 412px) 100vw, 412px\" \/><\/p><p>On d\u00e9terminise l\u2019automate\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10439 size-medium\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image32-300x208.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"300\" height=\"208\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image32-300x208.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image32.png 563w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3cfc050 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3cfc050\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6b80a34\" data-id=\"6b80a34\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-55a9385 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"55a9385\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e6e9c52 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e6e9c52\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-86cae1c\" data-id=\"86cae1c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-be4419e elementor-widget elementor-widget-heading\" data-id=\"be4419e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Exercice 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f657127 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f657127\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-44a30fe\" data-id=\"44a30fe\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-8a43b32 elementor-widget elementor-widget-text-editor\" data-id=\"8a43b32\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On consid\u00e8re la grammaire r\u00e9guli\u00e8re G = (\u0393,\u03a3,S,\u03a0) avec \u0393 = {S,P,R},\u03a3= {a,b} et \u03a0 = {S \u2192 P,P \u2192 baR,P \u2192 aS,R \u2192 bb,R \u2192 aP}. Trouver une expression r\u00e9guli\u00e8re pour ce langage. \u00a0Construire un automate A acceptant le langage d\u00e9fini par la grammaire G. Donner explicitement A sous la forme (Q,\u03a3,q0,F,\u2206). \u00a0\u00a0Trouver un automate d\u00e9terministe acceptant ce langage.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2856b33 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2856b33\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7ca40db\" data-id=\"7ca40db\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b0b6bc9 elementor-widget elementor-widget-toggle\" data-id=\"b0b6bc9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1851\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1851\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1851\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1851\"><p>On utilise les m\u00eames lettres S, P et R pour les langages accept\u00e9 \u00e0 partir des \u00e9tats S, P et R. Ces langages satisfont le syst\u00e8me d\u2019\u00e9quations:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10440 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image33.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"175\" height=\"60\" title=\"\"><\/p><p>La premi\u00e8re \u00e9quation donne S = P, en substituant les expressions pour S et R dans la deuxi\u00e8me \u00e9quation on obtient P = aP + ba(aP + bb) ce qui est \u00e9quivalent \u00e0 P = (a + baa)P + babb. Ici, P agit comme un \u00e9tat de d\u00e9part car il existe que une espilon transition entre S et P.<\/p><p>On r\u00e9sout cette derni\u00e8re \u00e9quation: P = (a+baa)\u2217babb, d\u2019o\u00f9 L(A) = S = P = (a+baa)\u2217babb.<\/p><p>Partir du l\u2019automate de Thompson pour arriver \u00e0\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10441 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image34.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"553\" height=\"237\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image34.png 553w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image34-300x129.png 300w\" sizes=\"(max-width: 553px) 100vw, 553px\" \/><\/p><p>En d\u00e9terminisant l\u2019automate A on obtient B (pour plus de faciliter, il est parfois utile de mettre un \u00e9tat poubelle prenant les interactions sans n\u0153uds d\u2019arriv\u00e9):<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10442 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image35.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"449\" height=\"282\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image35.png 449w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image35-300x188.png 300w\" sizes=\"(max-width: 449px) 100vw, 449px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-95afeca elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"95afeca\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a1b7ee9\" data-id=\"a1b7ee9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bb0ae7c elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"bb0ae7c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-bac5216 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bac5216\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-fc58008\" data-id=\"fc58008\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0c199ec elementor-widget elementor-widget-heading\" data-id=\"0c199ec\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Exercice 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-20c859e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"20c859e\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-135317e\" data-id=\"135317e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5dc8e68 elementor-widget elementor-widget-text-editor\" data-id=\"5dc8e68\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Construire un automate fini d\u00e9terministe correspondant \u00e0 chaque automate ci-dessous, et calculez une expression r\u00e9guli\u00e8re pour le langage accept\u00e9 \u00e0 l\u2019aide de la grammaire associ\u00e9e :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10443 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image36.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"522\" height=\"140\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image36.png 522w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image36-300x80.png 300w\" sizes=\"(max-width: 522px) 100vw, 522px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-dd3665d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"dd3665d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-db1821c\" data-id=\"db1821c\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-c6dd093 elementor-widget elementor-widget-toggle\" data-id=\"c6dd093\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2081\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2081\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2081\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2081\"><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10444 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image37.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"489\" height=\"301\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image37.png 489w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image37-300x185.png 300w\" sizes=\"(max-width: 489px) 100vw, 489px\" \/><\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10445 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image38.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"654\" height=\"250\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image38.png 654w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image38-300x115.png 300w\" sizes=\"(max-width: 654px) 100vw, 654px\" \/><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-edafe4b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"edafe4b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-04ea4ca\" data-id=\"04ea4ca\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-001776d elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"001776d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c911b24 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c911b24\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-a62ee10\" data-id=\"a62ee10\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4f31ac1 elementor-widget elementor-widget-heading\" data-id=\"4f31ac1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-6\"><\/span>Exercice 6<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-21180af elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"21180af\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8e53175\" data-id=\"8e53175\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-d693ad7 elementor-widget elementor-widget-text-editor\" data-id=\"d693ad7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Un barman aveugle joue au jeu suivant avec un client : il a devant lui un plateau sur lequel sont dispos\u00e9s quatre verres formant un carr\u00e9. Chacun de ces verres peut \u00eatre retourn\u00e9 ou non, sans que le barman ne le sache. Le but de ce dernier est de s\u2019arranger pour que tous les verres soient tourn\u00e9s dans le m\u00eame sens. Pour ce faire, il peut \u00e0 chaque tour choisir l\u2019une des trois actions suivantes : $<\/p><ul><li>tourner l\u2019un des verres<\/li><li>tourner deux verres voisins<\/li><li>tourner deux verres oppos\u00e9s<\/li><\/ul><p>mais pour corser la difficult\u00e9, le client peut tourner le plateau d\u2019un nombre quelconque de quart de tours entre chacune des actions du barman. Le jeu s\u2019arr\u00eate d\u00e8s qu\u2019une des deux positions gagnantes est atteinte.<\/p><p>Montrer qu\u2019on peut restreindre \u00e0 quatre le nombre de configurations diff\u00e9rentes, puis repr\u00e9senter les actions possibles du jeu par un automate non d\u00e9terministe.<\/p><p>D\u00e9terminiser cet automate et en d\u00e9duire une strat\u00e9gie gagnante pour le bar.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-34a1f20 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"34a1f20\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-55be4ae\" data-id=\"55be4ae\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2b3a357 elementor-widget elementor-widget-toggle\" data-id=\"2b3a357\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-4531\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-4531\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-4531\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-4531\"><p>Seules quatre configurations sont possibles :<\/p><p>-les quatre verres sont tous dans le m\u00eame sens (configuration q0)<\/p><p>-trois verres sont dans un sens et le quatri\u00e8me dans l\u2019autre sens (configuration q1)<\/p><p>-deux verres voisins sont dans un sens et les deux autres dans l\u2019autre sens (configuration q2)<\/p><p>-deux verres oppos\u00e9s sont dans un sens et les deux autres dans l\u2019autre sens (configuration q3).<\/p><p>On d\u00e9signe par la lettre :<\/p><p>-a le fait de changer l\u2019orientation d\u2019un des quatre verres<\/p><p>-b le fait de changer l\u2019orientation de deux verres voisins<\/p><p>-c le fait de changer l\u2019orientation de deux verres oppos\u00e9s.<\/p><p>Le jeu peut alors \u00eatre repr\u00e9sent\u00e9 par l\u2019automate non d\u00e9terministe suivant\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10446 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image39.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"293\" height=\"256\" title=\"\"><\/p><p>Sa d\u00e9terminisation conduit \u00e0 l\u2019automate suivant\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10447 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image40.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"668\" height=\"250\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image40.png 668w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image40-300x112.png 300w\" sizes=\"(max-width: 668px) 100vw, 668px\" \/><\/p><p>On constate que le mot reconnu cbcacbc conduit \u00e0 une position gagnante pour le barman.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1233305 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1233305\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f2759e7\" data-id=\"f2759e7\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-aa06c49 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"aa06c49\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ac4bc93 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ac4bc93\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0ca9539\" data-id=\"0ca9539\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bee774e elementor-widget elementor-widget-heading\" data-id=\"bee774e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Minimisation\"><\/span>Minimisation<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-60ee425 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"60ee425\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c550db4\" data-id=\"c550db4\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-28361e1 elementor-widget elementor-widget-heading\" data-id=\"28361e1\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-7\"><\/span>Exercice 7<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6326a25 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6326a25\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-57b1c1a\" data-id=\"57b1c1a\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-fe76bf0 elementor-widget elementor-widget-text-editor\" data-id=\"fe76bf0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>On consid\u00e8re l\u2019automate A = ({a, b}, {1, 2, 3}, \u2206, {1}, {1}) suivant :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10448 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image41.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"257\" height=\"162\" title=\"\"><\/p><p>Donnez la table d\u00e9crivant \u2206. Le mot baabab est-il accept\u00e9 par l\u2019automate A (v\u00e9rifier en d\u00e9roulant la grammaire que vous aurez pr\u00e9alablement \u00e9crite)? \u00a0Donnez l\u2019automate fini d\u00e9terministe minimal qui reconnait le m\u00eame langage que A.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-8daa5ab elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8daa5ab\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-9b85e4b\" data-id=\"9b85e4b\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-758c7d3 elementor-widget elementor-widget-toggle\" data-id=\"758c7d3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1231\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1231\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1231\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1231\"><p>\u2206 = {(1, a, 2),(1, b, 1),(1, b, 3),(2, a, 1),(2, a, 3),(3, b, 1)}<\/p><p>baabab n\u2019est pas accept\u00e9 par l\u2019automate. On peut ajouter un puits, not\u00e9 #, \u00e0 l\u2019automate pour le rendre complet. L\u2019arbre de lecture est alors le suivant\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10449 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image42.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"152\" height=\"244\" title=\"\"><\/p><p>Aucune feuille ne correspond \u00e0 un \u00e9tat final, notons que toutes les feuilles finissent dans le puits.<\/p><p>L\u2019automate d\u00e9terministe :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10450 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image43.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"257\" height=\"126\" title=\"\"><\/p><p>Les \u00e9tats {1} et {1,3} ont les m\u00eames r\u00e8gles. On trouve donc l\u2019automate minimal\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10451 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image44.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"241\" height=\"91\" title=\"\"><\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7b6843d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7b6843d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-b34f12e\" data-id=\"b34f12e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-bf4837d elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"bf4837d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-dc43f3d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"dc43f3d\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-98c4e39\" data-id=\"98c4e39\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0d7b068 elementor-widget elementor-widget-heading\" data-id=\"0d7b068\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-8\"><\/span>Exercice 8<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4215ded elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4215ded\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-71ce80f\" data-id=\"71ce80f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-e3abbec elementor-widget elementor-widget-text-editor\" data-id=\"e3abbec\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Parmi les expressions rationnelles et les automates suivants dire quels sont les automates et les expressions rationnelles qui repr\u00e9sentent le m\u00eame langage\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10452 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image45.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"558\" height=\"247\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image45.png 558w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image45-300x133.png 300w\" sizes=\"(max-width: 558px) 100vw, 558px\" \/><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-be5ea46 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"be5ea46\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-f4df646\" data-id=\"f4df646\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5a0279b elementor-widget elementor-widget-toggle\" data-id=\"5a0279b\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-9431\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-9431\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-9431\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-9431\"><p>On souhaite comparer les quatre langages. On calcule l\u2019automate minimal de chaque langage. Il suffira ensuite de comparer ces automates. En effet l\u2019automate minimal est un objet canonique ne d\u00e9pendant que du langage, deux langages sont donc \u00e9gaux si ils ont le m\u00eame automate minimal (modulo renommage des \u00e9tats).<\/p><p>1 &#8211; Expression Rationnelle (ab\u2217a + b(a + b))\u2217\u00a0. On commence par construire un automate par une m\u00e9thode au choix :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10453 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image46.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"257\" height=\"232\" title=\"\"><\/p><p>On souhaite maintenant construire l\u2019automate minimal du langage. Pour cela il faut d\u2019abord d\u00e9terminiser puis minimiser l\u2019automate ci-dessus. Par chance on a d\u00e9j\u00e0 un automate d\u00e9terministe, on peut donc directement passer \u00e0 l\u2019algorithme de minimisation qui nous donne le r\u00e9sultat suivant :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10454 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image47.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"150\" height=\"144\" title=\"\"><\/p><p>2 &#8211; Expression Rationnelle (ab + b(a + b))\u2217\u00a0. On commence par construire un automate par la m\u00e9thode de Glushkov :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10455 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image48.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"253\" height=\"211\" title=\"\"><\/p><p>De m\u00eame l\u2019automate est d\u00e9j\u00e0 d\u00e9terministe. Apr\u00e8s minimisation nous avons l\u2019automate suivant\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10456 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image49.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"121\" height=\"143\" title=\"\"><\/p><p>3 &#8211; Pour minimiser A3, on doit d\u2019abord le d\u00e9terminiser. Voici le r\u00e9sultat de l\u2019algorithme de d\u00e9terminisation :<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10457 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image50.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"205\" height=\"117\" title=\"\"><\/p><p>Et apr\u00e8s minimisation\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10458 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image51.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"135\" height=\"141\" title=\"\"><\/p><p>4 &#8211; \u00a0L\u2019automate est d\u00e9j\u00e0 d\u00e9terministe, apr\u00e8s minimisation nous obtenons\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10459 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image52.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"143\" height=\"141\" title=\"\"><\/p><p>Maintenant que nous avons construit l\u2019automate minimal pour chacun des quatre langages, on peut les comparer. On constate que modulo renommage des \u00e9tats les langages de A3 et (ab + b(a + b))\u2217\u00a0ont le m\u00eame automate minimal et sont donc \u00e9gaux. Il en va de m\u00eame pour les langages de A4 et (ab\u2217a + b(a + b))\u2217\u00a0.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-030b9f7 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"030b9f7\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-2ff8dd3\" data-id=\"2ff8dd3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7596620 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"7596620\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ada5412 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ada5412\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-527b7bb\" data-id=\"527b7bb\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-685da75 elementor-widget elementor-widget-heading\" data-id=\"685da75\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-9\"><\/span>Exercice 9<span class=\"ez-toc-section-end\"><\/span><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6a605e6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6a605e6\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-8193809\" data-id=\"8193809\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-de0b422 elementor-widget elementor-widget-text-editor\" data-id=\"de0b422\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p>Soit \u03a3 = {a,b}, on consid\u00e8re deux langages suivants : L, le langage form\u00e9 de tous les mots de \u03a3\u2217\u00a0contenant aba; M, le langage d\u00e9fini par l\u2019expression r\u00e9guli\u00e8re (b + aa\u2217\u00a0bb) \u2217\u00a0(\u03b5\u00a0+ aa\u2217\u00a0+ aa\u2217\u00a0b).<\/p><p>\u00a0Donner un automate non d\u00e9terministe reconnaissant L. D\u00e9terminer l\u2019automate minimal A reconnaissant L.<\/p><p>Donner un automate non d\u00e9terministe avec \u03b5\u00a0-transitions reconnaissant M. D\u00e9terminer l\u2019automate minimal B reconnaissant M.<\/p><p>En comparant les deux automates obtenus A et B d\u00e9duire que L = compl\u00e9mentaire(M). En termes d\u2019automate, le compl\u00e9mentaire d\u2019un automate A revient \u00e0 rendre les \u00e9tats entrants en \u00e9tats terminaux et vice-versa.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-be8a65a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"be8a65a\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-48a07f0\" data-id=\"48a07f0\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b91912a elementor-widget elementor-widget-toggle\" data-id=\"b91912a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1941\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1941\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1941\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1941\"><p>Apr\u00e8s avoir d\u00e9terminer le langage ou grammaire de L, on forme l\u2019automate pour la m\u00e9thode de Glushkov\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10460 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image53.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"255\" height=\"98\" title=\"\"><\/p><p>Puis on le d\u00e9terminise\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10461 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image54.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"350\" height=\"114\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image54.png 350w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image54-300x98.png 300w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><\/p><p>On renomme les \u00e9tats dans l\u2019ordre par A, B, C, D, E, F pour \u00e9viter les ambigu\u00eft\u00e9s. Puis on minimise\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10462 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image55.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"284\" height=\"112\" title=\"\"><\/p><p>De m\u00eame pour l\u2019automate reconnaissant M\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10463 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image56.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"289\" height=\"143\" title=\"\"><\/p><p>On le d\u00e9terminisme (on remarquera que l\u2019on forme un \u00e9tat poubelle)\u00a0:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-10464 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/10\/Image57.png\" alt=\"exercices corrig\u00e9s sur l&#039;optimisation des automates, la d\u00e9terminisation et la minimisation\" width=\"248\" height=\"117\" title=\"\"><\/p><p>On renomme les \u00e9tats dans l\u2019ordre par K, L, M, N pour \u00e9viter les ambig\u00fcit\u00e9s. L\u2019automate est d\u00e9j\u00e0 minimal.<\/p><p>On constate que la seule diff\u00e9rence entre les automates d\u00e9terministes A et B est que les \u00e9tats finals de l\u2019un sont non-finals dans l\u2019autre. D\u2019o\u00f9 on peut d\u00e9duire que leurs langages sont compl\u00e9mentaires.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Language theory Home page Wiki Corrected exercises You will find on this page corrected exercises on the optimization of automata, determinization and minimization. \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":5028,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-10427","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10427","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=10427"}],"version-history":[{"count":14,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10427\/revisions"}],"predecessor-version":[{"id":20574,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10427\/revisions\/20574"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/5028"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=10427"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}