Server : Apache System : Linux webd348.cluster026.gra.hosting.ovh.net 5.15.148-ovh-vps-grsec-zfs-classid #1 SMP Thu Feb 8 09:41:04 UTC 2024 x86_64 User : hednacluml ( 122243) PHP Version : 8.3.9 Disable Function : _dyuweyrj4,_dyuweyrj4r,dl Directory : /home/hednacluml/encyclo/articles/t/h/é/ |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr" lang="fr" dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<!-- headlinks removed -->
<link rel="shortcut icon" href="../../../../misc/favicon.ico"/>
<title>Théorie des automates finis - Wikipédia</title>
<style type="text/css">/*<![CDATA[*/ @import "../../../../skins/offline/main.css"; /*]]>*/</style>
<link rel="stylesheet" type="text/css" media="print" href="../../../../skins/common/commonPrint.css" />
<!--[if lt IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE50Fixes.css";</style><![endif]-->
<!--[if IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE55Fixes.css";</style><![endif]-->
<!--[if IE 6]><style type="text/css">@import "../../../../skins/monobook/IE60Fixes.css";</style><![endif]-->
<!--[if IE]><script type="text/javascript" src="../../../../skins/common/IEFixes.js"></script>
<meta http-equiv="imagetoolbar" content="no" /><![endif]-->
<script type="text/javascript" src="../../../../skins/common/wikibits.js"></script>
<script type="text/javascript" src="../../../../skins/offline/md5.js"></script>
<script type="text/javascript" src="../../../../skins/offline/utf8.js"></script>
<script type="text/javascript" src="../../../../skins/offline/lookup.js"></script>
<script type="text/javascript" src="../../../../raw/gen.js"></script> <style type="text/css">/*<![CDATA[*/
@import "../../../../raw/MediaWiki%7ECommon.css";
@import "../../../../raw/MediaWiki%7EMonobook.css";
@import "../../../../raw/gen.css";
/*]]>*/</style> </head>
<body
class="ns-0">
<div id="globalWrapper">
<div id="column-content">
<div id="content">
<a name="top" id="contentTop"></a>
<h1 class="firstHeading">Théorie des automates finis</h1>
<div id="bodyContent">
<h3 id="siteSub">Un article de Wikipédia, l'encyclopédie libre.</h3>
<div id="contentSub"></div>
<!-- start content -->
<div class="plainlinks bandeau-niveau-ebauche bandeau">
<table style="background-color:transparent">
<tr>
<td class="bandeau-icone">
<div style="text-align:center;white-space:nowrap"><a href="../../../../articles/c/r/y/Image%7ECrystal_mycomputer.png_ff1d.html" class="image" title="Crystal mycomputer.png"><img alt="" src="../../../../images/shared/thumb/e/e3/Crystal_mycomputer.png/35px-Crystal_mycomputer.png" width="35" height="35" border="0" /></a></div>
</td>
<td>
<div class="bandeau-titre"><strong>Cet article est une <a href="../../../../articles/%C3%A9/b/a/Aide%7E%C3%89bauche_a94d.html" title="Aide:Ébauche">ébauche</a> concernant l’<a href="../../../../articles/i/n/f/Portail%7EInformatique_2d39.html" title="Portail:Informatique">informatique</a>.</strong></div>
<div class="bandeau-texte">Vous pouvez partager vos connaissances en l’améliorant. <b>(<a href="../../../../articles/c/o/m/Aide%7EComment_modifier_une_page_32be.html" title="Aide:Comment modifier une page">Comment ?</a>)</b>.</div>
</td>
</tr>
</table>
</div>
<table id="toc" class="toc" summary="Sommaire">
<tr>
<td>
<div id="toctitle">
<h2>Sommaire</h2>
</div>
<ul>
<li class="toclevel-1"><a href="#Langages_formels"><span class="tocnumber">1</span> <span class="toctext">Langages formels</span></a>
<ul>
<li class="toclevel-2"><a href="#Alphabet"><span class="tocnumber">1.1</span> <span class="toctext">Alphabet</span></a></li>
<li class="toclevel-2"><a href="#Mot"><span class="tocnumber">1.2</span> <span class="toctext">Mot</span></a></li>
</ul>
</li>
<li class="toclevel-1"><a href="#D.C3.A9finitions"><span class="tocnumber">2</span> <span class="toctext">Définitions</span></a>
<ul>
<li class="toclevel-2"><a href="#Automate_fini"><span class="tocnumber">2.1</span> <span class="toctext">Automate fini</span></a></li>
<li class="toclevel-2"><a href="#Chemin"><span class="tocnumber">2.2</span> <span class="toctext">Chemin</span></a></li>
<li class="toclevel-2"><a href="#Accessibilit.C3.A9"><span class="tocnumber">2.3</span> <span class="toctext">Accessibilité</span></a></li>
<li class="toclevel-2"><a href="#D.C3.A9terminisme"><span class="tocnumber">2.4</span> <span class="toctext">Déterminisme</span></a></li>
</ul>
</li>
<li class="toclevel-1"><a href="#Voir_aussi"><span class="tocnumber">3</span> <span class="toctext">Voir aussi</span></a></li>
</ul>
</td>
</tr>
</table>
<script type="text/javascript">
//<![CDATA[
if (window.showTocToggle) { var tocShowText = "afficher"; var tocHideText = "masquer"; showTocToggle(); }
//]]>
</script>
<p><a name="Langages_formels" id="Langages_formels"></a></p>
<h2><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Langages formels">modifier</a>]</span> <span class="mw-headline">Langages formels</span></h2>
<p><a name="Alphabet" id="Alphabet"></a></p>
<h3><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Alphabet">modifier</a>]</span> <span class="mw-headline">Alphabet</span></h3>
<p>On appelle <b>alphabet</b> tout ensemble <span class="texhtml">Σ</span> fini, non vide. Les éléments de <span class="texhtml">Σ</span> sont appelés <b>lettres</b>.</p>
<p><a name="Mot" id="Mot"></a></p>
<h3><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Mot">modifier</a>]</span> <span class="mw-headline">Mot</span></h3>
<p>On appelle <b>mot</b> toute suite d'éléments de <img class="tex" alt="\Sigma ^{\N}" src="../../../../math/7/c/7/7c7f7869f1823017f9be69928b771d0e.png" /> à support fini, on pose <span class="texhtml">ε</span> la suite vide dit le <b>mot vide</b>. L'ensemble des mots sur <span class="texhtml">Σ</span> est noté <span class="texhtml">Σ <sup>*</sup></span> .</p>
<p>L'opération fondamentale sur les mots est la <b>concaténation</b>, notée <img class="tex" alt="\cdot" src="../../../../math/3/6/f/36f8ae4c86b69d52d037a6802d91cc4a.png" />, elle est définie ainsi :</p>
<p>Soit deux mots <span class="texhtml"><i>u</i> = (<i>a</i><sub>1</sub>,...,<i>a</i><sub><i>n</i></sub>)</span> et <span class="texhtml"><i>v</i> = (<i>b</i><sub>1</sub>,...,<i>b</i><sub><i>n</i></sub>)</span>.</p>
<p>On a alors,</p>
<ul>
<li><img class="tex" alt="u \cdot \epsilon = \epsilon \cdot u =u" src="../../../../math/7/7/f/77fd4ed086a70e98e452f4ab6d209153.png" /></li>
<li><img class="tex" alt="u \cdot v = (a_{1},...,a_{n},b_{1},...,b_{n})" src="../../../../math/4/9/2/49264e02e68a3f51c9626c6f0b63d69f.png" /></li>
</ul>
<p>La concaténation est <b>associative</b> : <img class="tex" alt="u \cdot{} (v \cdot w) = (u \cdot v) \cdot w" src="../../../../math/3/a/1/3a18e27599df439e8ced1f987708d0a5.png" /></p>
<p>Par conséquent :</p>
<p><img class="tex" alt="(\Sigma^{*}, \cdot)" src="../../../../math/3/c/8/3c83307f87f9c4cffeaf96524e4e7fd4.png" /> est un <b>monoïde</b>, c’est-à-dire que <img class="tex" alt="\cdot" src="../../../../math/3/6/f/36f8ae4c86b69d52d037a6802d91cc4a.png" /> est associative et possède pour élément neutre <img class="tex" alt="\epsilon \in \Sigma^{*}" src="../../../../math/3/3/f/33f95fd3bae047bb2080310aaab6c9a9.png" />.</p>
<p><a name="D.C3.A9finitions" id="D.C3.A9finitions"></a></p>
<h2><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Définitions">modifier</a>]</span> <span class="mw-headline">Définitions</span></h2>
<p><a name="Automate_fini" id="Automate_fini"></a></p>
<h3><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Automate fini">modifier</a>]</span> <span class="mw-headline">Automate fini</span></h3>
<p>On appelle <b><a href="../../../../articles/a/u/t/Automate_fini.html" title="Automate fini">automate fini</a></b> le quintuplet <span class="texhtml"><i>A</i> = < Σ,<i>Q</i>,δ,<i>I</i>,<i>F</i> ></span> , où :</p>
<ul>
<li><span class="texhtml">Σ</span> est un alphabet,</li>
<li><span class="texhtml"><i>Q</i></span> est un ensemble d'états stables,</li>
<li><span class="texhtml"><i>I</i></span> est une partie de <span class="texhtml"><i>Q</i></span> appelée ensemble des états initiaux,</li>
<li><span class="texhtml"><i>F</i></span> est une partie de <span class="texhtml"><i>Q</i></span> appelée ensemble des états finaux,</li>
<li><span class="texhtml">δ</span> est une partie de <img class="tex" alt="Q \times \Sigma \times Q" src="../../../../math/5/0/b/50bc6442499fbc8cbc7db5ba81d0909f.png" /> appelée ensemble des transitions. C'est une fonction de transition qui à un état du système et un élément de l'alphabet associe le passage à un autre état.</li>
</ul>
<p><a name="Chemin" id="Chemin"></a></p>
<h3><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Chemin">modifier</a>]</span> <span class="mw-headline">Chemin</span></h3>
<p>Un <b>chemin</b> est une suite de flèches consécutives. On note un chemin :</p>
<p><img class="tex" alt="(q_0, a_1, q_1)\cdots(q_{k-1}, a_k, q_k)" src="../../../../math/0/e/8/0e8bcf08d856bc39a0a66dad2115b2ae.png" />, avec <img class="tex" alt="q_i \in Q" src="../../../../math/f/9/9/f99943b09a87c083442a3bd88f353a91.png" />, <img class="tex" alt="a_i \in \Sigma" src="../../../../math/b/0/9/b0919ed50284f030b2f4f2569df5bf30.png" />, <img class="tex" alt="(q_{i-1}, a_i, q_i) \in \delta" src="../../../../math/a/8/9/a897d96e735bf7ab5625d9f65b72ab99.png" />.</p>
<p>On appelle <b>trace</b> ou <b>étiquette</b> la suite de lettres reconnue <img class="tex" alt="a_1\cdots a_k" src="../../../../math/b/2/a/b2a2c277f864736282a1737e0bf35905.png" /></p>
<p>On dit qu'un chemin est <b>réussi</b> lorsque <img class="tex" alt="q_0 \in I" src="../../../../math/d/5/e/d5e664edd721cea81a99ffb975369e2b.png" /> et <img class="tex" alt="q_k \in F" src="../../../../math/0/7/a/07ae9804b5c4724407a2f31296eb4780.png" /></p>
<p>Un mot est <b>reconnu</b> lorsqu'il est l'étiquette d'un chemin réussi.</p>
<p><a name="Accessibilit.C3.A9" id="Accessibilit.C3.A9"></a></p>
<h3><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Accessibilité">modifier</a>]</span> <span class="mw-headline">Accessibilité</span></h3>
<p>Un état, <img class="tex" alt="q\in Q" src="../../../../math/0/3/a/03ab662b71a6e9ecc0a51e8938a9f26b.png" />, est dit :</p>
<ul>
<li><b>accessible</b> si et seulement s'il existe un chemin partant d'un état initial et allant jusqu'à <span class="texhtml"><i>q</i></span> ;</li>
<li><b>coaccessible</b> si et seulement s'il existe un chemin partant de l'état <span class="texhtml"><i>q</i></span> et allant jusqu'à un état final.</li>
</ul>
<p>Un automate est dit :</p>
<ul>
<li>accessible si et seulement si tous ses états sont accessibles ;</li>
<li>coaccessible si et seulement si tous ses états sont coaccessibles ;</li>
<li>émondé s'il est accessible et coaccessible.</li>
</ul>
<p><a name="D.C3.A9terminisme" id="D.C3.A9terminisme"></a></p>
<h3><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Déterminisme">modifier</a>]</span> <span class="mw-headline">Déterminisme</span></h3>
<p>Un automate est <b>déterministe</b> si et seulement s'il possède un seul état initial et pour chaque état, il existe au plus une flèche sortante pour chaque lettre, c’est-à-dire si <img class="tex" alt="\forall q\in Q,\forall a\in \Sigma, |\delta(q,a)| \leq 1" src="../../../../math/6/5/b/65b69feeecf6abea0cedcd069005e6ec.png" /></p>
<p><a name="Voir_aussi" id="Voir_aussi"></a></p>
<h2><span class="editsection">[<a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html" title="Modifier la section : Voir aussi">modifier</a>]</span> <span class="mw-headline">Voir aussi</span></h2>
<ul>
<li><a href="../../../../articles/a/u/t/Automate_fini.html" title="Automate fini">Automate fini</a></li>
<li><a href="../../../../articles/a/u/t/Automate_%C3%A0_pile.html" title="Automate à pile">Automate à pile</a></li>
<li><a href="../../../../articles/a/u/t/Automate_d%27arbres.html" title="Automate d'arbres">Automate d'arbres</a></li>
</ul>
<!--
NewPP limit report
Preprocessor node count: 372/1000000
Post-expand include size: 2379/2048000 bytes
Template argument size: 687/2048000 bytes
Expensive parser function count: 2/500
-->
<div class="printfooter">
</div>
<div id="catlinks"><div id='catlinks' class='catlinks'><div id="mw-normal-catlinks"><a href="../../../../articles/a/c/c/Cat%C3%A9gorie%7EAccueil_1aae.html" title="Catégorie:Accueil">Catégorie</a> : <span dir='ltr'><a href="../../../../articles/i/n/f/Cat%C3%A9gorie%7EInformatique_th%C3%A9orique_644b.html" title="Catégorie:Informatique théorique">Informatique théorique</a></span></div><div id="mw-hidden-catlinks" class="mw-hidden-cats-hidden">Catégorie cachée : <span dir='ltr'><a href="../../../../articles/w/i/k/Cat%C3%A9gorie%7EWikip%C3%A9dia%7E%C3%A9bauche_informatique_1039.html" title="Catégorie:Wikipédia:ébauche informatique">Wikipédia:ébauche informatique</a></span></div></div></div> <!-- end content -->
<div class="visualClear"></div>
</div>
</div>
</div>
<div id="column-one">
<div id="p-cactions" class="portlet">
<h5>Views</h5>
<ul>
<li id="ca-nstab-main"
class="selected" ><a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_automates_finis.html">Article</a></li><li id="ca-talk"
class="new" ><a href="../../../../articles/t/h/%C3%A9/Discuter%7ETh%C3%A9orie_des_automates_finis_09b6.html">Discussion</a></li><li id="ca-current"
><a href="http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_automates_finis">Version actuelle</a></li> </ul>
</div>
<div class="portlet" id="p-logo">
<a style="background-image: url(../../../../misc/Wiki.png);"
href="../../../../index.html"
title="Accueil"></a>
</div>
<script type="text/javascript"> if (window.isMSIE55) fixalpha(); </script>
<div class='portlet' id='p-navigation'>
<h5>Navigation</h5>
<div class='pBody'>
<ul>
<li id="n-mainpage"><a href="../../../../index.html">Accueil</a></li>
<li id="n-thema"><a href="../../../../articles/a/c/c/Portail%7EAccueil_bcc9.html">Portails thématiques</a></li>
<li id="n-alphindex"><a href="../../../../articles/t/o/u/Special%7EToutes_les_pages_fabc.html">Index alphabétique</a></li>
<li id="n-randompage"><a href="../../../../articles/p/a/g/Special%7EPage_au_hasard_9c81.html">Un article au hasard</a></li>
<li id="n-contact"><a href="../../../../articles/c/o/n/Wikip%C3%A9dia%7EContact_929e.html">Contacter Wikipédia</a></li>
</ul>
</div>
</div>
<div class='portlet' id='p-Contribuer'>
<h5>Contribuer</h5>
<div class='pBody'>
<ul>
<li id="n-help"><a href="../../../../articles/s/o/m/Aide%7ESommaire_c9f0.html">Aide</a></li>
<li id="n-portal"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_5272.html">Communauté</a></li>
<li id="n-recentchanges"><a href="../../../../articles/m/o/d/Special%7EModifications_r%C3%A9centes_b222.html">Modifications récentes</a></li>
<li id="n-aboutwp"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_des_nouveaux_arrivants_0784.html">Accueil des nouveaux arrivants</a></li>
<li id="n-sitesupport"><a href="http://meta.wikimedia.org/wiki/Faire_un_don:_explication">Faire un don</a></li>
</ul>
</div>
</div>
<div id="p-search" class="portlet">
<h5><label for="searchInput">Rechercher</label></h5>
<div id="searchBody" class="pBody">
<form action="javascript:goToStatic(3)" id="searchform"><div>
<input id="searchInput" name="search" type="text"
accesskey="C" value="" />
<input type='submit' name="go" class="searchButton" id="searchGoButton"
value="Aller" />
</div></form>
</div>
</div>
</div><!-- end of the left (by default at least) column -->
<div class="visualClear"></div>
<div id="footer">
<div id="f-poweredbyico"><a href="http://www.mediawiki.org/"><img src="../../../../skins/common/images/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" /></a></div> <div id="f-copyrightico"><a href="http://wikimediafoundation.org/"><img src="../../../../misc/wikimedia-button.png" border="0" alt="Wikimedia Foundation"/></a></div> <ul id="f-list">
<li id="f-credits">Cette page a été modifiée pour la dernière fois le 2 avril 2008 à 04:51 par Utilisateur <a href="../../../../articles/a/l/e/Utilisateur%7EAlecs.bot_6f7d.html" title="Utilisateur:Alecs.bot">Alecs.bot</a>. Basé sur le travail de Utilisateur(s) <a href="../../../../articles/d/u/m/Utilisateur%7EDumZiBoT_1015.html" title="Utilisateur:DumZiBoT">DumZiBoT</a>, Moeknepti, <a href="../../../../articles/z/x/8/Utilisateur%7EZX81-bot_0db4.html" title="Utilisateur:ZX81-bot">ZX81-bot</a>, Olivier Gauwin, <a href="../../../../articles/o/u/t/Utilisateur%7EOuts_7cbf.html" title="Utilisateur:Outs">Outs</a>, <a href="../../../../articles/b/a/y/Utilisateur%7EBayo_acb4.html" title="Utilisateur:Bayo">Bayo</a>, <a href="../../../../articles/c/h/a/Utilisateur%7EChaoborus_2b04.html" title="Utilisateur:Chaoborus">Chaoborus</a>, Kaelkael, <a href="../../../../articles/j/a/i/Utilisateur%7EJaimie_Ann_Handson_690c.html" title="Utilisateur:Jaimie Ann Handson">Jaimie Ann Handson</a>, <a href="../../../../articles/d/u/r/Utilisateur%7EDurandal_e1b4.html" title="Utilisateur:Durandal">Durandal</a>, <a href="../../../../articles/l/m/a/Utilisateur%7ELmaltier_4140.html" title="Utilisateur:Lmaltier">Lmaltier</a> et <a href="../../../../articles/s/u/r/Utilisateur%7ESurfeurnet_c527.html" title="Utilisateur:Surfeurnet">Surfeurnet</a> et Utilisateur(s) non enregistré(s) de Wikipédia.</li> <li id="f-copyright"><span style="white-space:normal"><a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Droit_d'auteur" title="Droit d'auteur">Droit d'auteur</a> : Tous les textes sont disponibles sous les termes de la <a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Licence_de_documentation_libre_GNU" title="GFDL">licence de documentation libre GNU</a> (GFDL).<br/>
Wikipedia® est une marque déposée de la <a href="http://wikimediafoundation.org/wiki/Accueil" title="Wikimedia Foundation">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a class="internal" href="http://en.wikipedia.org/wiki/501(c)" title="501(c)">501(c)(3)</a> du code fiscal des États-Unis.</span><br/></li> <li id="f-about"><a href="../../../../articles/%C3%A0/_/p/Wikip%C3%A9dia%7E%C3%80_propos_5de1.html" title="Wikipédia:À propos">À propos de Wikipédia</a></li> <li id="f-disclaimer"><a href="../../../../articles/a/v/e/Wikip%C3%A9dia%7EAvertissements_g%C3%A9n%C3%A9raux_fef1.html" title="Wikipédia:Avertissements généraux">Avertissements</a></li> </ul>
</div>
</div>
</body>
</html>