Correction td 2 : automates finis Théorie des langages-...

Théorie des langages : Correction td 2 : automates finis

Télécharger PDF

Université Sidi Mohamed Ben Abdellah

    École Nationale des Sciences Appliquées

    Année Universitaire : 2019-2020

    Module : Théorie des Langages

    Filière : GINF - 1ère Année

    Professeur : [Nom non précisé]
Correction - TD 2 : Automates FinisExercice 1On considère deux automates A1 et A2 sur l’alphabet {a, b}.
1. Les transitions suivantes sont données pour l’automate A1 :
a → état 1
ab → état 2
abb → état 2
abba → état 2
ε (mot vide) → état 0
2. Les mots reconnus par l’automate A1 sont : ab, abb et abba.
3. Lorsque la lecture du mot aab est effectuée par l’automate A1, il se bloque dans l’état 1.
4. Pour les mots suivants :
ab2b → oui (reconnu par A1)
a2b4 → non
b3a2 → oui (reconnu par A1)
b4 → non
5. Pour le mot b3a2, l’automate A2 se trouve dans l’état 1.
6. S’il n’a lu aucun a, l’automate A2 reste toujours dans l’état 0.
7. L’automate A2 atteint l’état final 2 si le mot contient au moins un ab.
Langages associés aux automates A1 et A2L(A1) = {a} ∙ {b} ∙ {(a ∪ b)}* ou L(A1) = {abw | w ∈ {a, b}*}.
L(A2) = {b}* ∙ {a} ∙ {a}* ∙ {b} ∙ {(a ∪ b)}* ou L(A2) = {bnambw | w ∈ {a, b}*, n ≥ 0, m ≥ 0}.
Exercices supplémentairesExercice 2Les langages suivants sont définis :
L1 = {ε} (mot vide uniquement)
L2 = {ε, a, ab} (mot vide, a et ab)
L3 = {ai | i ≥ 0} (tous les mots composés uniquement de a)
L4 = {aibjc2k | k, i ≥ 0, j > 1} (mots avec au moins deux b et un nombre pair de c)
L5 = Les mots de {a, b}* ne contenant pas la chaîne bba.
L6 = {w, w ∈ {a, b}* | |wa| = [2−3]} (mots avec un nombre de a entre 2 et 3 inclus).
L7 = Les entiers naturels multiples de 2 (représentés en binaire).
L8 = a+b* (mots commençant par au moins un a suivi de zéros ou plus de b).
L9 = {ab}{a, c}{b}+3 (mots de la forme ab suivi de a ou c, puis au moins trois b).
L10 = ((a+ba*)+ + (ab + b*))* (mots avec des sous-chaînes valides selon les règles données).
L11 = a(ab + b*)(aba)*.
L12 = (ab + a)* + (aba*b + ba)*.
Remarque : Vous pouvez utiliser l’algorithme de déterminisation pour convertir les automates finis non déterministes (AFN) de L10, L11 et L12 en automates finis déterministes (AFD) correspondants.
Exercice 3Problème des déplacements avec des contraintes :
4 types de déplacements (transitions) possibles :
H : l’homme traverse seul
HC : l’homme traverse avec la chèvre
HL : l’homme traverse avec le loup
HX : l’homme traverse avec le chou
L’AFN modélise les entités situées de chaque côté de la rivière à un moment donné.
Exercice 41. Les mots appartenant à L : aa.
Les mots n’appartenant pas à L : abba, aabbbab, abbbbba.
2. L = {w ∈ {a, b}* | |wa| = |wb| + 2(2k + 1), k ∈ ℤ} (mots où le nombre de a est supérieur au nombre de b selon une formule donnée).
3. AFD reconnaissant les mots de L avec les états {N, E, S, O} et l’alphabet {a, b}, les transitions et l’état final S.
Exercice 5AFN :
Le langage associé : L = ({ab} ∪ {ε}) ∙ {a}+ ∪ {a, b}* ∙ {b} (mots commençant par ab ou ε, suivis d’un ou plusieurs a, ou contenant des a et b suivis d’un b).
Exercice 6AFN :
Table de transitions :

      
        [0-9]
        [1-9]
        +
        ,
        0
      

        1
        1
        1
        3
        2
      

        2
        {2,3}
        4
        4
        4
      

        4
        4
        4
        5
        4
      

        5
        5
        5
        5
        5
      
Exercice 7AFN :
Exercice 81. L’expression régulière : ab(a*b).
2. L’ensemble des mots proches de L peut être représenté par les expressions régulières suivantes : ab(a*b), ab(a*a), ab(a*ba*b), aa(a*b), bb(a*b).
L’expression régulière combinée pour tous les mots proches de L est : ab(a*b) + ab(a*a) + ab(a*ba*b) + aa(a*b) + bb(a*b).

[0-9]	[1-9]	+	,	0
1	1	1	3	2
2	{2,3}	4	4	4
4	4	4	5	4
5	5	5	5	5

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 se compose d’un ensemble d’états, d’un alphabet, d’une fonction de transition déterministe et d’un état final. Pour chaque symbole de l’alphabet et chaque état, il existe une seule transition possible.

Comment construire un automate fini non déterministe (AFN) à partir d’une expression régulière ?

Pour convertir une expression régulière en AFN, on utilise généralement l’algorithme de Thompson. Cet algorithme construit un AFN en associant des nœuds et des transitions pour chaque opérateur et symbole de l’expression régulière.

Quelle est la différence entre un langage reconnu par un AFD et un AFN ?

Un AFD et un AFN peuvent reconnaître le même langage. Cependant, un AFD a une seule transition possible pour chaque symbole et état, tandis qu’un AFN peut avoir plusieurs transitions ou une transition ε (vide) à partir d’un même état et symbole.

Correction td 2 : automates finis Théorie des langages-...