Td 1 automate fini déterministe Théorie des langages-té...

Théorie des langages : Td 1 automate fini déterministe

Télécharger PDF

TD 1 - Automate Fini Déterministe (AFD)

Qu 1. Donner la table de transition de l’AFD suivant et déterminer le langage reconnu

12 ab ba

Pour cet automate, la table de transition est la suivante :

   État   a   b
   1      2   1
   2      2   4
   3      3   3
   4      3   3

L’état initial est 1 et l’état final est 4.

Le langage reconnu par cet automate est : L = {a, ab, ba, baba, abab}

Qu 2. Déterminer le langage reconnu par l’automate suivant et construire l’automate qui reconnaît son complémentaire

aaa

L’automate suivant reconnaît le langage : L = {aaa}.

Pour construire un AFD qui reconnaît le complémentaire {a,b}∗ \ L, on utilise la méthode de complétion par ajout d’un état final unique et de transitions vers cet état pour tous les mots non reconnus.

Qu 3. Dessiner l’AFD et déterminer le langage reconnu

Soit l’AFD ({a,b}, {1,2,3,4}, δ, 1, {4}) avec δ donnée par la table suivante :

   État   a   b
   1      2   1
   2      2   4
   3      3   3
   4      3   3

Le langage reconnu par cet AFD est : L = {a, ab, ba, baba, abab}.

Qu 4. Donner les expressions régulières et construire des AFD

a. L = {ε} → Expression régulière : ε ou ∅ (selon contexte).

b. L = φ → Expression régulière : ∅.

c. L = {a,b}∗ → Expression régulière : (a + b)*.

d. L = {ab}{a,c}{b}+ → Expression régulière : ab(a + c)b+.

e. L = {a,b}∗ {a}{a,b}² → Expression régulière : (a + b)* a (a + b)².

f. L₁ = {a,bb}∗, L₂ = {b}∗ {{a}{b}∗ {a}}∗ {b}∗ et L₁ ∩ L₂ → Expression régulière pour L₁ ∩ L₂ : {b}∗.

Qu 5. Langage fini X = {aa, abaaa, abab}

a. Pref(X) = {ε, a, aa, ab, aba, abaa, abaaa}.

b. Un AFD qui reconnaît X peut être construit en utilisant les états suivants :

   État   a   b
   1      2   3
   2      4   5
   3      3   3
   4      4   3
   5      5   3

États finaux : {2, 4, 5}.

c. Généralisation : Tout ensemble fini de mots est régulier car il peut être représenté par une expression régulière de la forme L = w₁ + w₂ + ... + wₙ, où wᵢ sont les mots de l’ensemble fini.

d. Un AFD qui reconnaît {a,b}∗ X peut être construit en ajoutant un état initial qui pointe vers l’AFD de X, puis en permettant toutes les transitions possibles vers cet état initial.

Qu 6. Montrer que les langages suivants ne sont pas rationnels

a. L = {aᵖ : p premier} → Ce langage n’est pas rationnel car il n’existe pas d’automate fini qui puisse reconnaître tous les mots dont la longueur est un nombre premier.

b. L = {w ∈ {a,b}∗ : |a(w)| = |b(w)|} → Ce langage n’est pas rationnel car il nécessite de compter le nombre de 'a' et de 'b' dans un mot, ce qui ne peut pas être fait par un automate fini.

FAQ

Qu’est-ce qu’un automate fini déterministe (AFD) ?

Un AFD est un modèle mathématique utilisé pour reconnaître des langages formels. Il est composé d’un ensemble fini d’états, d’un alphabet, d’une fonction de transition déterministe et d’un ensemble d’états finaux.

Comment construire un AFD pour un langage donné ?

Pour construire un AFD, on définit les états, les transitions entre eux en fonction des symboles de l’alphabet, l’état initial et les états finaux. Chaque état doit avoir une transition unique pour chaque symbole.

Qu’est-ce qu’un langage régulier ?

Un langage est régulier s’il peut être reconnu par un automate fini (déterministe ou non). Cela signifie qu’il existe une expression régulière qui décrit ce langage.