Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Page 1 sur 1 Exercice 01 : 1) Supprimer les-transitions de telle sorte on obti

Page 1 sur 1 Exercice 01 : 1) Supprimer les-transitions de telle sorte on obtient un AEF simple équivalent à cet AEFPG. 2) L’automate obtenu est déterministe ? Si oui, pourquoi?, sinon le déterminiser. Exercice 02 : 1) Proposer un automate d’états finis simple pour chacun des langages et expressions ci-dessous. E1 = (ab)+(aa+b)* E2 = b*(aab)* E3 = a*+ (bb)* E4 = (a + b+)a*b+ L1 = {an bm , tel que n, m 0 et m = 0 si n est pair et m=1 si n est impair} L2 = {w{a,b}*, tel que |w|a pair et |w|b est pair} L3 = {w{a,b}*, tel que w ne contient pas 3b consécutifs} L4 = {w{a,b}* /(w commence par a ou finit par b) et tout a est directement suivi d’au moins deux b} 2) Indiquer, si possible, les opérations sur les AEF pour obtenir chacun des langages suivants : L5 = {w{a,b}* / w contient aa et un nombre pair de a} L6 = {w{a,b}* / w contient aa ou un nombre pair de a} L7 = {w{a,b}*, tel que w contient un nombre de a multiple de 3 et multiple de 2} L8 = {w{a,b}*, tel que w contient un nombre de a multiple de 2 et non multiple de 3} L9 = {Tous les mots sur {a, b, c} qui ne contiennent ni le facteur aba ni le facteur bca} L10 = {w{a,b}*, tel que w contient la sous chaîne aaa ou bbb mais pas les deux en même temps} L11 = {w{a,b}* / w contient une seule fois la sous chaîne abba, et, la sous chaîne bb ne figure pas dans w en dehors de abba} L12 = { w{a,b}*, tel que le nombre d’occurrences de a dans w = le nombre d’occurrences de b dans w} Exercice 03 : 1) Trouver l’expression régulière du langage reconnu par cet AEF. Exercice 04 : 1) Donner l’AEF généralisé associé à cette grammaire régulière généralisée à droite G       S , / bB / aB B , b / abB / aS / bbA A , A / aS S , b , a , B A, S,      2) Donner la grammaire régulière généralisée à droite associée à cet AEF généralisé Bonne suite T D N° 04 : Le passage entre les automates d’états finis, les langages réguliers, les expressions régulières et les grammaires régulières Année universitaire : 2015/2016 Université de Batna Département d’informatique 2èmeannée licence informatique Module : Théorie des langages uploads/s3/ td04-tl.pdf