Remerciez-le!

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

TLA TIC-1 Tek-up 2020/2021 1 TD 1 Mot, langages et expressions régulières Exerc

TLA TIC-1 Tek-up 2020/2021 1 TD 1 Mot, langages et expressions régulières Exercice 1 : Décrire les langages définis par les expressions régulières suivantes : 1. travailler(ai ∪ as ∪ a ∪ ons ∪ ez ∪ ont) La conjugaison du verbe travailler au futur simple 2. (- ∪ ε)(0∪1 ∪2 ∪3∪4∪5 ∪6∪7∪8∪9) (0∪1 ∪2 ∪3∪4∪5 ∪6∪7∪8∪9)* Vérifier si une entrée de programme est bien un entier 3. 0(0∪1 ∪2 ∪3∪4∪5 ∪6∪7∪8∪9) ∪ (10∪11∪12) H (0∪1 ∪2 ∪3∪4∪5) (0∪1 ∪2 ∪3∪4∪5 ∪6∪7∪8∪9) Afficher l’heure sur 12h de la forme hhHmm Exercice 2 : Soit l'alphabet Σ = {a,b} Donner les expressions régulières qui génèrent les langages suivants : L1 = {ω∈ Σ*, tel que ω contient seulement 3b, le reste c'est des a's} ➥ER1 = a*ba*ba*ba* L2 = {ω∈ Σ*, tel que ω contient un nombre de a divisible par 3} ➥ER2 = (b*ab*ab*ab*)*∪b* L3 = {ω∈ Σ*, tel que ω contient un nombre pair de a} ➥ER3 = (b*(ab*a)*b*)* L4 = {ω∈ Σ*, tel que ω contient un nombre impair de b} ➥ER4= a*b (a*(ba*b)*a*)* L5 = {ω∈ Σ*, tel que ω contient le sous mot aaa ou le sous mot bbb mais pas les deux en même temps} L5 = L6∪ L7 avec TLA TIC-1 Tek-up 2020/2021 2 L6 = {ω∈ Σ*, tel que w contient la sous chaîne aaa mais pas la sous chaîne bbb} L7 = {ω∈ Σ*, tel que w contient la sous chaîne bbb mais pas la sous chaîne aaa} ER6 = (a ∪ ba ∪ bba)*(ε ∪ b ∪ bb) aaa (a ∪ ba ∪ bba)*(ε ∪ b ∪ bb) ER7 = (b ∪ ab ∪ aab)*(ε ∪ a ∪ aa) bbb b ∪ ab ∪ aab)*(ε ∪ a ∪ aa) ➥ER5 = ER6∪ER7 Exercice 3: Soit Σ = {a,b} On définit récursivement les mots du langage S définit sur Σ* comme suit : w est un mot de S si et seulement si : w=b ou w=w1aw2, avec w1 et w2 des mots de S. 1. Déterminer les mots de S de longueur ≤ 5. 2. Démontrer que tout mot w de S s’écrit sous la forme : w = b(ab)n pour n ≥ 0. 3. Démontrer que tout mot w = b (ab)n pour n ≥ 0, est un mot de S. 4. Que peut-on déduire ? S= {w ∈ Σ* / w = b ou w = w1 a w2 et w1 ∈ S et w2 ∈ S} 1) L’ensemble des mots de S de longueur ≤ 5 = {b, bab, babab} 2) Par induction sur les longueurs des mots : Pour L0 = 1 ∃ w ∈ S |w| = L0 et ∃ n ≥ 0 w = b(ab)n = b, n = 0 On suppose qu’on a∀ k L0≤k<L (∃ w∈S |w|=k ⇒ ∃ m≥0 w=b(ab)m) (i) Soit w ∈ S, |w| =L Mq ∃ n ≥ 0 w = b(ab)n On a w ∈ S donc w = w1aw2/ w1 ∈ S et w2 ∈ S, |w1| < |w| et |w2| < |w| |w1| < L et |w2| < L alors d’après (i) ∃ h1 ≥ 0 w1 = b(ab)h1 et ∃ h2 ≥ 0 w2 = b(ab)h2 w = b(ab)h1ab(ab)h2 = b(ab)h1+h2+1 C.-à-d. ∃n≥0 w=b(ab)n avec n=h1+h2+1 Donc tout mot w de S s’écrit sous la forme : w = b(ab)n pour n ≥ 0 3) Pour n0=0, on a b(ab)n0=b(ab)0 =b ∈ S Supposons que la propriété est vraie pour n ≥ 0 montrons que c’est vrai pour n+1 C.-à-d. on a b(ab)n ∈ S Mq b(ab)n+1∈ S b(ab)n+1 = b(ab)(ab)n = ba(b(ab)n) ∈ S car b ∈ S et b(ab)n ∈ S donc ba(b(ab)n) ∈ S (w1 = b et w2 = b(ab)n ) TLA TIC-1 Tek-up 2020/2021 3 4) On déduit que S = {b(ab)n , n ≥0} uploads/s3/ td1-corr.pdf