Théorie des langages : Td 3 automates deterministes et non deterministes
Télécharger PDFISG, Année Universitaire : 2011/2012 Théorie des Langages et des Automates : (2
ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI
- TD : M. Badr MEFTAHI _________________________________________________________________________________________________________________ Série N°3 : AEF Déterministes et non Déterministe
Exercice 1Proposer un automate pour chacun des langages suivants : L1 = {wÎ{a,b}*, w contient un nombre pair de a et un nombre paire de b} L
2 = {wÎ Σ*: w divisible par 3} : 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 2Pour l’expression régulière suivante : (a
* | b* ) (of) * Faire : 1) Construire, selon l’algorithme donné en cours, l’automate correspondant. 2) Donner les suites de transitions pour le traitement du mot w
1 = bbbofof et du mot w
2 = 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 w
1 avec la nouvelle version de l’automate. Que remarquez-vous ?
Exercice 3Soit 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 4Soit 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) 5 - 4 3 1) Présenter le diagramme de transition de A. 2) Présenter le diagramme de transition de A déterministe et minimal.