Théorie des langages : Td 3 automates deterministes et non deterministes
Télécharger PDFSérie N°3 : Automates Déterministes et Non Déterministes
Exercice 1
Proposer un automate pour chacun des langages suivants :
L1 = {w ∈ {a,b}*, w contient un nombre pair de a et un nombre pair de b}
L2 = {w ∈ Σ*, la somme des chiffres est divisible par 3} : (aide : classer les chiffres en 3 classes ceux dont mod 3 = 0, ceux dont mod 3 = 1 et ceux dont mod 3 = 2).
Exercice 2
Pour l’expression régulière suivante : (a* | b*) (of)*
1) Construire, selon l’algorithme donné en cours, l’automate correspondant.
2) Donner les suites de transitions pour le traitement du mot w1 = bbbofof et du mot w2 = aabof (il s’agit de simuler le travail de reconnaissance élaboré par l’automate).
1) Rendre l’automate déterministe et minimal.
2) Donner alors la suite de transitions pour le traitement du mot w1 avec la nouvelle version de l’automate. Que remarquez-vous ?
Exercice 3
Soit r = (12)+ 2+ 1+ | (1221)+
1) Proposer deux mots reconnus par le langage décrit par r de cardinalité égale à 20 et 30.
2) Proposer un automate pour r (sans nécessairement suivre l’algorithme du cours à la lettre).
3) Si votre automate est non déterministe, alors le rendre déterministe et minimal si nécessaire. En présenter le diagramme de transition.
4) Proposer une grammaire pour le langage décrit par r.
5) Vérifier que vos deux mots proposés dans la question n°1 sont bien générés par votre grammaire.
Exercice 4
Soit l’automate A suivant :
Q \ V
T a b 0 1 1 (initial) 2 1 3 - 2 2 1 3 - 3 5 - 3 4 4 5 - 4 3 5 (final)
1) Présenter le diagramme de transition de A.
2) Présenter le diagramme de transition de A déterministe et minimal.
FAQ
Qu’est-ce qu’un automate déterministe ?
Un automate déterministe est un modèle de reconnaissance de langage où chaque état a une seule transition possible pour chaque symbole de l’alphabet.
Comment construire un automate minimal à partir d’un automate non déterministe ?
Pour rendre un automate déterministe et minimal, on utilise des techniques comme la suppression des états inutiles et la fusion des états équivalents.
À quoi sert la grammaire dans l’étude des langages ?
Une grammaire permet de décrire la structure syntaxique d’un langage formel et de générer des mots valides, tout comme un automate peut le reconnaître.