Remerciez-le!

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

Devoir informatique theorique

IFT- Informatique Théorique Devoir À remettre le octobre avant h Question Construisez des automates ?nis qui acceptent les langages suivants Les automates peuvent être non-déterministes si cela vous simpli ?e la t? che Par contre vous ne pouvez pas utiliser des transitions étiquetées par un mot voir p des notes de cours ou par une expression régulière ? L ? ensemble des mots sur l ? alphabet o? tous les s ? il y en a apparaissent par groupe de trois Notons que des groupes successifs de sont possibles c ? est à dire des blocs de de longueur etc Ainsi est un mot qui appartient au langage parce qu ? il contient un bloc de trois et ensuite deux blocs consécutifs de trois Par contre et ne font pas partie du langage ? L a a an n ?? N ?? ai ?? a b ?? i pair ? ai b En d ? autres mots L contient les mots non-vides o? toutes les lettres en position paire sont des b Question Donnez des expressions régulières qui représentent les deux langages de la question Question Construisez un automate déterministe qui accepte le même langage que l ? automate non-déterministe ci-dessous Question Pour les deux questions suivantes on ?xe l ? alphabet à a b Pour un mot w ?? a b ? on dé ?nit w appelons w le négatif de w comme étant le mot obtenu à partir de w en remplaçant les a par des b et les b par des a Voici une liste d ? exemples si w aba alors w bab si w aa alors w bb si w bbba alors w aaab si w ? alors w ? Montrez que le langage suivant n ? est pas régulier K ww w ?? a b ? En d ? autres mots K est l ? ensemble des mots qui peuvent être coupés en deux moitiés ou la seconde est le négatif de la première Par exemple ababab aabb et bbbaaaab font partie de K mais babb aaba et aba ne font pas partie de K CQuestion Soit L ? a b ? Par extension de la dé ?nition de la question précédente on pose L w w ?? L Par exemple si L ab bab bbb alors L ba aba aaa Montrez que si L est un langage régulier alors L est aussi un langage régulier Il y a deux façons principales de procéder La première est de montrer comment on peut partir d ? un automate M qui accepte L et le modi ?er pour obtenir un automate M qui accepte L La seconde est de montrer comment on peut partir d ? une expression régulière r qui représente L et la modi ?er pour obtenir une expression régulière r qui représente L Question Soit ? l ? alphabet de symboles Un mot w ?? ? ? de longueur n peut-être vu à la fois comme une suite de n colonnes de bits