Théorie des automates finis

Théorie des automates finis
Article principal : Automate fini.

Cet article décrit la théorie des automates finis, cas particulier de la théorie des automates.

Sommaire

Langages formels

Alphabet

On appelle alphabet tout ensemble Σ fini, non vide. Les éléments de Σ sont appelés lettres.

Mot

On appelle mot toute suite d'éléments de \Sigma ^{\N} à support fini, on pose \epsilon la suite vide dit le mot vide. L'ensemble des mots sur Σ est noté Σ * .

L'opération fondamentale sur les mots est la concaténation, notée \cdot, elle est définie ainsi :

Soit deux mots u = (a1,...,an) et v = (b1,...,bn).

On a alors,

  • u \cdot \epsilon = \epsilon \cdot u =u
  • u \cdot v = (a_{1},...,a_{n},b_{1},...,b_{n})

La concaténation est associative : u \cdot{} (v \cdot w) = (u \cdot v) \cdot w

Par conséquent :

(\Sigma^{*}, \cdot) est un monoïde, c’est-à-dire que \cdot est associative et possède pour élément neutre \epsilon \in \Sigma^{*}.

Définitions

Automate fini

On appelle automate fini le quintuplet A = < Σ,Q,δ,I,F > , où :

  • Σ est un alphabet,
  • Q est un ensemble d'états stables,
  • I est une partie de Q appelée ensemble des états initiaux,
  • F est une partie de Q appelée ensemble des états finaux,
  • δ est une partie de Q \times \Sigma \times Q 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.

Chemin

Un chemin est une suite de flèches consécutives. On note un chemin :

(q_0, a_1, q_1)\cdots(q_{k-1}, a_k, q_k), avec q_i \in Q, a_i \in \Sigma, (q_{i-1}, a_i, q_i) \in \delta.

On appelle trace ou étiquette la suite de lettres reconnue a_1\cdots a_k

On dit qu'un chemin est réussi lorsque q_0 \in I et q_k \in F

Un mot est reconnu lorsqu'il est l'étiquette d'un chemin réussi.

Accessibilité

Un état, q\in Q, est dit :

  • accessible si et seulement s'il existe un chemin partant d'un état initial et allant jusqu'à q ;
  • coaccessible si et seulement s'il existe un chemin partant de l'état q et allant jusqu'à un état final.

Un automate est dit :

  • accessible si et seulement si tous ses états sont accessibles ;
  • coaccessible si et seulement si tous ses états sont coaccessibles ;
  • émondé s'il est accessible et coaccessible.

Déterminisme

Un automate est déterministe 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 \forall q\in Q,\forall a\in \Sigma, |\delta(q,a)| \leq 1

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorie des automates finis de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Theorie des automates finis — Théorie des automates finis Sommaire 1 Langages formels 1.1 Alphabet 1.2 Mot 2 Définitions 2.1 Automate fini …   Wikipédia en Français

  • Theorie des automates — Théorie des automates Pour les articles homonymes, voir Théorie et Automate. La théorie des automates, intimement liée à l étude des langages formels, est une branche de l informatique théorique qui étudie la puissance de calcul de divers modèles …   Wikipédia en Français

  • Théorie des automates — Pour les articles homonymes, voir Théorie et Automate. En informatique théorique, la théorie des automates est l étude de machines abstraites définissant un modèle de calcul[H 1]. Cette théorie est le fondement de branches très importantes de l… …   Wikipédia en Français

  • Théorie des expressions rationnelles — Langage rationnel Pour les articles homonymes, voir Langage, Régulier et Rationnel. Les expressions rationnelles permettent d engendrer une famille de langages appelés, suivant les auteurs, langages rationnels ou langages réguliers. Ce sont les… …   Wikipédia en Français

  • Théorie des langages et automates — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… …   Wikipédia en Français

  • Theorie des langages — Théorie des langages La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d un point de vue mathématique. Un langage est un ensemble de mots. Un mot (ou lexème) est une… …   Wikipédia en Français

  • Théorie des langages — En informatique, la théorie des langages a pour objectif de décrire les langages formels, vus comme moyen de communication, d un point de vue mathématique. Un langage formel[1] est un ensemble de mots. Un mot est une suite finie de symboles. L… …   Wikipédia en Français

  • Automates cellulaires — Automate cellulaire À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe !) de l… …   Wikipédia en Français

  • Machine à états finis — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Transducteur à états finis — En informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction maladroite de l anglais finite state transducer) est un automate fini avec… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”