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 avec correction compilation

TD CExercice I Trouvez les langages correspondants aux dé ?nitions suivantes ?? Tous les mots sur a b c qui commencent par un a et ?nissent par un b ?? Tous les mots sur a b qui contiennent plus de a que de b On note par Pref L l ? ensemble suivant u m L u est pré ?xe de m et par Suf L l ? ensemble suivant v m L v est su ?xe de m ?? Calculez Pref L et Suf L dans chacun des cas suivants L ab ac L anbm n m ? On note par Conj m l ? ensemble des conjugués de m Trouvez Conj m pour m et m anbn Deux mots m et m ? sont dits conjugués s ? il existe deux mots u et v tels que m uv et m ? vu CCorrection ? Les langages correspondants aux dé ?nitions suivantes ?? Tous les mots sur a b c qui commencent par a et ?nissent par b L m m a a b c b ?? Tous les mots sur a b qui contiennent plus de a que de b L m m a m b ? Calculer Pref L et Suf L dans chacun des cas suivants ?? L ab ac Pref L a ab ac et Suf L b c ab ac ?? L n m ? Posons m tel que ? r ? n et ? k ? m donc Pref L et Suf L ? Trouvez Conj m pour m et m ? m Conj m ? m Conj m CExercice ? Soient L L et L trois langages Démontrer les propriétés suivantes L L ?? L non idempotence L L ?? L L non commutativité L L L L L L associativité L L UL L L U L L distributivité de la concaténation union L L ??L L L ?? L L distributivité de la concaténation intersection CCorrection ? Soient L L et L trois langages Démontrer les propriétés suivantes L L ?? L non idempotence Avec un contre-exemple L a L L aa ?? a et L a Donc la concaténation des langages n ? est idempotente L L ?? L L non commutativité Avec un contre-exemple L a L b L L ab ?? L L ba la concaténation des langages n ? est pas commutative L L L L L L associativité L L L xyz x L et y L et z L L L L xyz x L et yz L L L L L xyz xy L L et z L Pr conséquent la concaténation est associative CCorrection L L UL L L U L L distributivité de la concaténation union Soit w y L ?? L x LL UeLt y ??L iol eux ixs teL xeyttyq wL x ??y ewt x xLy eLt Ly oL uou w xy L L w L L U L L Donc la concaténation est distributive par rapport à