Remerciez-le!

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

Td1 2 Théorie des Langages ?? TD et ALPHABETS LANGAGES ET GRAMMAIRES Exercice - On considère l ? alphabet X a b c On rappelle que w représente la longueur du mot w et représente le mot vide Soit deux mots w ababc et q caba Calculez w w et w Calculez wq w

Théorie des Langages ?? TD et ALPHABETS LANGAGES ET GRAMMAIRES Exercice - On considère l ? alphabet X a b c On rappelle que w représente la longueur du mot w et représente le mot vide Soit deux mots w ababc et q caba Calculez w w et w Calculez wq w Calculez w ab ab et ab aba Donnez les pré ?xes les pré ?ces propres les suf ?xes et les suf ?xes propres de q Donnez le miroir du mot wq Exercice - Montrez qu ? il ne peut y avoir de mot x tel que ax xb Quels sont les deux langages dont la fermeture par l ? étoile donne le langage uniquement composé du mot vide Les mots suivants sont-ils générés par le langage ab ? b ? a aa ba abbb ababb baba Même question avec le langage ab ? b ? Exercice - On considère l ? alphabet X a b Donner les langages correspondant aux propriétés suivantes les mots qui ne contiennent aucun b les mots qui ne contiennent pas ab les mots qui contiennent au moins un a les mots de longueur paire Exercice - On considère l ? alphabet X a b c Calculez les ensembles X X et X Pour chacun des ensembles suivants caractérisez L ? et calculez L ?? L L ?? L L L L L L ab bb et L a ab bbc ca L et L bbc ca L et L bbc ca L ab bb et L X ? Soient L et L L w ?? X ? w n avec n ?? N L w ?? X ? w n avec n ?? N Caractérisez en français les langages L ?? L L ?? L Exercice - On considère l ? alphabet X a b et les langages L et L suivants L anbn n ?? N L bnan n ?? N Calculez L ?? L L ?? L L L L L L CExercice - On considère des langages sur un alphabet quelconque Démontrez les propriétés suivantes L ? L ?? L L ? L L L L ?? L L L ?? L L Montrez que L L ?? L ? L L ?? L L A l ? aide d ? un contre-exemple montrez que l ? égalité n ? est pas forcément atteinte Montrez que L ?? L ? ? L ? ?? L ? A l ? aide d ? un contre-exemple montrez que l ? égalité n ? est pas forcément atteinte Exercice - On considère des langages sur un alphabet X quelconque Soient les deux langages suivants Lp w w est paire Li w w estimpaire Montrez que L p Lp Montrez que L p Lp puis que L ? p Lp Montrez que Lp Li Li Lp Li Montrez que Li Lp puis que Li ? X ? Exercice - Soient les langages L L et L construits sur l ? alphabet X a b