Fiche de révision : Langages et automates des SED

📋 Plan du Cours

1. Événements et systèmes discrets
2. Alphabet, mots et langages
3. Opérations sur les mots
4. Opérations sur les langages
5. Langages réguliers
6. Définition des automates
7. Propriétés et déterminisation
8. Langages reconnus par automates

📖 1. Événements et systèmes discrets

🔑 Notions clés & Définitions

• Événement : Changement d’état instantané, sans durée, d’une variable logique, numérique ou de type tableau, qui présente un intérêt.
• Occurrence d’événement : Réalisation particulière d’un événement donné.
• Système à événements discrets : Système à espace d’état discret dont tous les changements d’état se produisent seulement lors d’occurrences d’événements asynchrones.

★ À maîtriser

📌 Toutes les occurrences d’événements sont asynchrones et deux occurrences non corrélées ne peuvent pas se produire à la même date.

Compléments

• Dans un système à événements discrets, le temps est dense et appartient à R+.

• Dans un SED, deux occurrences d’un même événement peuvent conduire à des états différents, tandis que des occurrences d’événements différents peuvent conduire au même état.

💡 Astuce mémo

Occurrence asynchrone → changement d’état

📖 2. Alphabet, mots et langages

🔑 Notions clés & Définitions

• Alphabet : Ensemble fini d’événements ou de symboles.
• Mot : Séquence d’événements appartenant à un alphabet.
• Langage : Ensemble de mots formés à partir des éléments d’un alphabet Σ.
• Fermeture de Kleene : Le langage Σ* est l’ensemble de tous les mots pouvant être définis sur l’alphabet Σ, y compris ε, et tout langage L défini sur Σ vérifie L ⊆ Σ*.

📝 Points essentiels

• La chaîne ε est la chaîne de longueur nulle.

💡 Astuce mémo

Un alphabet fournit les symboles qui s’enchaînent en mots puis en langages

📖 3. Opérations sur les mots

🔑 Notions clés & Définitions

• Concaténation : Mot u1u2 obtenu en plaçant u2 à la suite de u1.
• Taille d’un mot : La taille |x| d’un mot est son nombre de symboles ; ainsi, |0100| = 4, |abcab| = 5 et |ε| = 0.
• Puissance d’un alphabet : Σi est l’ensemble des mots formés par concaténation de i éléments de Σ, avec Σ0 = {ε}.

📝 Points essentiels

📐 Formule — La chaîne vide ε est l’élément neutre de la concaténation : $εu = uε = u$ pour tout mot u.

📌 Pour s = tuv, t est un préfixe, u est une sous-chaîne et v est un suffixe de s.

💡 Astuce mémo

Préfixe au début, sous-chaîne au milieu, suffixe à la fin

📖 4. Opérations sur les langages

🔑 Notions clés & Définitions

• Union de langages : L’union La ∨ Lb contient les mots qui appartiennent à La ou à Lb.
• Intersection de langages : L’intersection La ∧ Lb contient les mots qui appartiennent simultanément à La et à Lb.
• Concaténation de langages : La concaténation LaLb est l’ensemble des mots t qui s’écrivent t = ta tb avec ta ∈ La et tb ∈ Lb.
• Fermeture préfixielle : La fermeture préfixielle Pref(L) contient les préfixes de tous les mots de L, c’est-à-dire les mots t tels qu’il existe u ∈ Σ* avec tu ∈ L.

📝 Points essentiels

📌 Tout langage L est inclus dans sa fermeture préfixielle, et L est préfixe-clos si et seulement si L = Pref(L).

💡 Astuce mémo

Ensembles → concaténation → préfixes

📖 5. Langages réguliers

🔑 Notions clés & Définitions

• Langage régulier : Langage représentable par une expression régulière utilisant uniquement la sélection, la concaténation et l’itération.

★ À maîtriser

📌 Si r et s sont des expressions régulières, alors r+s, rs, r* et s* sont également des expressions régulières.

📌 Si L1 et L2 sont réguliers, leurs compléments, fermetures préfixielles, fermetures de Kleene, concaténation, union et intersection sont également réguliers.

Compléments

📌 Les expressions régulières de base ∅, ε et e représentent respectivement l’ensemble vide, {ε} et {e}, pour tout e ∈ Σ.

• La représentation par expression régulière fournit une représentation compacte d’un langage régulier.

💡 Astuce mémo

SCK : sélection, concaténation, Kleene

📖 6. Définition des automates

🔑 Notions clés & Définitions

• Automate à états fini : Un automate à états fini est défini par le 5-uplet ⟨X, Σ, δ, X0, M⟩.
• Composantes d’un automate : Dans ⟨X, Σ, δ, X0, M⟩, X est l’ensemble fini des états, Σ l’alphabet fini des événements, δ la fonction de transition de X×Σ vers X, X0 l’ensemble des états initiaux et M l’ensemble des états marqués.

📝 Points essentiels

• Pour reconnaître le code 5321, l’automate lit successivement les chiffres 5, 3, 2 puis 1, tandis qu’un chiffre incorrect conduit à une situation d’erreur.

💡 Astuce mémo

X-Σ-δ-X₀-M : états, alphabet, transitions, initiaux, marqués

📖 7. Propriétés et déterminisation

🔑 Notions clés & Définitions

• Accessibilité : Ensemble des états qu’il est possible d’atteindre à partir d’un état initial.
• Co-accessibilité : Ensemble des états à partir desquels il est possible d’atteindre un état marqué.
• Automate non déterministe : Un automate est non déterministe s’il possède plusieurs états initiaux ou si une même paire état-événement peut conduire à plusieurs états.

★ À maîtriser

📌 Un deadlock est un état non marqué sans transition sortante, tandis qu’un livelock est un ensemble d’états non marqués sans transition permettant d’en sortir.

• La déterminisation construit un automate déterministe équivalent en considérant les combinaisons d’états accessibles, en déterminant leurs transitions, puis en les représentant dans le nouvel automate.

Compléments

📌 La déterminisation d’un automate non déterministe peut augmenter le nombre d’états et de transitions.

💡 Astuce mémo

Accessible depuis l’initial, co-accessible vers le marqué

📖 8. Langages reconnus par automates

🔑 Notions clés & Définitions

• Langage reconnu : Ensemble des séquences d’occurrences d’événements, représentées par des mots, qui sont acceptées par cet automate.

★ À maîtriser

📌 Un alphabet est un ensemble d’événements, un mot est une séquence d’occurrences d’événements et un langage est un ensemble de telles séquences.

Compléments

• Les évolutions d’un automate sont provoquées par des séquences d’occurrences d’événements.

💡 Astuce mémo

Séquence d’événements → évolution de l’automate → mot reconnu

📊 Tableaux de synthèse

Notions fondamentales des langages