Remerciez-le!

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

Td04 tl Année universitaire Université de Batna Département d ? informatique èmeannée licence informatique Module Théorie des langages TD N Le passage entre les automates d ? états ?nis les langages réguliers les expressions régulières et les grammaires r

Année universitaire Université de Batna Département d ? informatique èmeannée licence informatique Module Théorie des langages TD N Le passage entre les automates d ? états ?nis les langages réguliers les expressions régulières et les grammaires régulières Exercice Supprimer les ? -transitions de telle sorte on obtient un AEF simple équivalent à cet AEFPG L ? automate obtenu est déterministe Si oui pourquoi sinon le déterminiser Exercice Proposer un automate d ? états ?nis simple pour chacun des langages et expressions ci-dessous E ab aa b E b aab E a bb E a b a b L an bm tel que n m ? et m si n est pair et m si n est impair L w ? a b tel que w a pair et w b est pair L w ? a b tel que w ne contient pas b consécutifs L w ? a b w commence par a ou ?nit par b et tout a est directement suivi d ? au moins deux b Indiquer si possible les opérations sur les AEF pour obtenir chacun des langages suivants L w ? a b w contient aa et un nombre pair de a L w ? a b w contient aa ou un nombre pair de a L w ? a b tel que w contient un nombre de a multiple de et multiple de L w ? a b tel que w contient un nombre de a multiple de et non multiple de L Tous les mots sur a b c qui ne contiennent ni le facteur aba ni le facteur bca L w ? a b tel que w contient la sous cha? ne aaa ou bbb mais pas les deux en même temps L w ? a b w contient une seule fois la sous cha? ne abba et la sous cha? ne bb ne ?gure pas dans w en dehors de abba L w ? a b tel que le nombre d ? occurrences de a dans w le nombre d ? occurrences de b dans w Exercice Trouver l ? expression régulière du langage reconnu par cet AEF Exercice Donner l ? AEF généralisé associé à cette grammaire régulière généralisée à droite G ? ?? ??S A B ? ?? a b ? ??S aS A A bbA aS abB b B aB bB ? ? S ?? Donner la grammaire régulière généralisée à droite associée à cet AEF généralisé Bonne suite Page sur C