Chapitre 1
Mots et langages
DR ING FATMA SOMAA
CPI2
Plan
1. Vocabulaire et Mot
2. Langage
3. Propriétés des langages
4. Operations sur les langages
5. Définition des langages
Vocabulaire et mot
Un alphabet (ou vocabulaire) est un ensemble fini, non vide de symboles. On le note généralement X ou
• Alphabet Latin ={a,b,c,…,z}
• Alphabet binaire ={0,1}
• ={rouge,noir,0,1,a}
Mot ou chaîne : Séquence de symboles de l’alphabet. Noté w.
• w1= voiture ; w2 = voyage deux mots définies sur l’alphabet Latin
• w1=00101 ; w2=101101 sont deux mots définies sur l’alphabet binaire.
• w1=noir01rouge ; w2=10AAnoir : sont deux mots définies sur l’alphabet ={rouge,noir,0,1,a}
Vocabulaire et mot
Taille d’un mot : |w|= nombre de symboles constituant le mot.
• |rouge|=5 en considérant l’alphabet Latin
• |001|=3 en considérant l’alphabet binaire
• |rouge|=1 en considérant l’alphabet ={rouge,noir,0,1,a}
Chaîne vide : notée e s’il n’appartient pas à l’alphabet ou ||=0.
Sous chaîne : x est une sous chaîne de w si il existe y et z (chaînes sur la même alphabet). Tel que w = y x z.
Vocabulaire et mot
Préfixe : x est un préfixe de w si il existe y tel que: w = x y.
Suffixe : x est un suffixe de w si il existe y tel que w = y x.
• x = voit est un préfixe de w = voiture, car il existe y = ure tel que w = voit ure = x y
• x = ture est un suffixe de w = voiture, car il existe y = voi tel que w = voi ture = x y
Exercice
Ex1: Donner les sous chaines wi associes aux mots suivants :
1) abba sur le vocabulaire {a, b}
2) (x1*(x2+x1)) sur le vocabulaire {x1, x2, +, *, (, )}
Ex2:
Quelle est la longueur des mots abba et sur le Vocabulaire {a,b}
Exercice corrigé
Ex1:
1) Si le vocabulaire X = {a, b} alors dans le mot abba,
w1 = a w2 = ab w3 = bb w4 = abba …..
2) Si le vocabulaire est X = {x1, x2, +, *, (, )} alors dans le mot (x1*(x2+x1))
w1 = ( w2 = x1 w3 = * w4 = ( w5 = x2
w6 = + w7 = x1 w8 = ) w9 = ) ….
Le mot abba est de longueur 4, |abba| = 4
Le mot e est de longueur 0, | |=0
Vocabulaire et mot
Nombre d’occurrences d’un symbole dans un mot :
Le nombre d’occurrences d’un symbole x dans un mot w est le nombre de fois ou ce symbole apparait
dans ce mot w. On le note |w|x .
Exercice :
Quel est le nombre d’occurrences de b dans les mots abba et
Corrige :
|abba|b=2
| |b=0
Langage
Ensemble de mots choisis dans un alphabet.
Un langage peut être infini mais il existe un nombre finie de symboles permettant de composer les
mots de ce langage.
∑k = ensemble des mots de longueur k avec des symboles de ∑
Exemple : ∑ ={0,1}
∑1 ={0,1}
∑2 ={00,01,10,11}
∑0 ={ε}
Langage
* Ensemble de toute les séquences de taille fini défini sur : Fermeture de l’alphabet.
*12...
12...
*
Un langage c’est un ensemble de mots appartenant à * et qui vérifie une propriété donnée :
L= {w * | w possède la propriété P}
Langage
Exemples
•Ensemble des mots anglais légales
• Ensemble des mots de l’alphabet binaire contenant un nombre de n de 0 suivie par le même nombre n
de 1.
L={ ; 01 ; 0011; 000111; … }.
• Ensemble des mots de l’alphabet binaire ayant un même nombre de 0 et de 1.
L={ ; 01 ; 10; 0101; 1001; … }.
• Ensemble des mots de l’alphabet binaire tel que leur valeur est premier.
L={ ; 10; 11; 101; 111; 1011; …}
Langage
Exemples
•Le langage vide L= ;
• Le langage {} contenant le mot vide.
◦ Note: {} .
◦ Note: L’alphabet est un ensemble fini.
• Ensemble des palindromes sur l’alphabet = {a,b}
◦ L = {w * | w = wR}
◦ L = {,aba,bab,a,b,…}
Propriétés des langages
•* est infinie et dénombrable.
• L = L1 L2 = {w * | w L1 ou w L2}
• L = L1 L2 = {w * | w L1 et w L2 }
• Concaténation :
L = L1 . L2 = L1L2={w * | x , y , w = x y , x L1, y L2 }
• Fermeture de Kleene.
◦ L* = {w *| w = w1w2…wk, k 0 et w1,w2,…,wk L}
◦ k = 0 w = ; k =1 w L ;
◦ Si L est un langage alors L* désigne l’ensemble de toute les chaînes de longueur finies formées par
concaténation de mots de L, où chaque mot peut être utilisé de 0 à n fois, la chaîne vide est inclus.
Propriétés des langages
•L M = M L.
Union est commutative.
• (L M) N = L (M N).
Union est associative.
• (LM)N = L(MN).
Concaténation est associative
Note: Concaténation n’est pas commutative, i.e.,
Il existe L et M tel que LM ML.
Exemple :
• L={aa,b}
• L*={,b,aa,bb,aab,baa,bbb,aaaa,aabb,baab,bbaa,bbbb,aaaab,aabaa,aabbb,baaaa,bbaab,bbbaa,bbbbb,…}
Note : * ={}
Propriétés des langages
•L(M N) = LM LN.
Concaténation est distributive à gauche pour l’union.
• (M N)L = ML NL.
Concaténation est distributive à droite pour l’union.
• L L = L.
Union est idempotente.
• * = {} , {}*={}
• L+ = LL* = L*L, L*= L+ {}
•(L*) *= L* . Fermeture est idempotente
Operations sur les langages
Concaténation : soient u et v deux mots définis sur l’alphabet , tel que :
ux1x2...xn v y1y2...ym
Concaténation est non commutative
wu.vx1x2...xn y1y2...ym
Propriétés :
• |w|=|uv|=|u|+|v|
• . Est associative
• est l’élément neutre pour la concaténation. x = x = x
Operations sur les langages
Facteur : soit u,v,w,t des mots définis sur tel que w = uvt
• si u = alors v est dit facteur gauche de w (ou préfixe).
• si t = alors v est dit facteur droit de w (ou suffixe).
• si u = t = alors w est un facteur de lui même.
Occurrence d’un symbole dans un mot :
|abaaba|a=4
Image (reverse) : w=aabab wR=babaa
Operations sur les langages
Facteur : soit u,v,w,t des mots définis sur tel que w = uvt
• si u = alors v est dit facteur gauche de w (ou préfixe).
• si t = alors v est dit facteur droit de w (ou suffixe).
• si u = t = alors w est un facteur de lui même.
Occurrence d’un symbole dans un mot :
|abaaba|a=4
Image (reverse) : w=aabab wR=babaa
Operations sur les langages
Operations sur les langages
Notation
Operations sur les langages
Exercice
Calculer A* pour chacun des ensembles A suivants:
A = {a}
corrigé
Operations sur les langages
Exercice
=
corrigé
Définition des langages
langages formels Tout sous ensemble de * dont les mots peuvent être définis de deux façons
Définition par propriété : Modélisation formelle d’une description naturel d’un langage.
Exemple :
L1 : {ensemble de mots définies sur {a,b} de longueur pair}
L1 = {w {a,b}* / |w| =2n ; n 0}
Définition des langages
Définition récursive : Définition dans laquelle, un langage est définie sur lui même.
L2={w *| w = a ou w = aw1; w1 L2}={a,aa,…,aaaa,…}
L3={w *| w = ou w = w1w2; |w1| =2 et w2 L3}
L3 L1
Définition des langages
Expressions régulières :
L4={,x,xx,xxx,xxxx,….}
soit S = {x} alors L4=S* ou L4={x}*
Considérons l’étoile de la fermeture de Kleene appliquée à la lettre x.
x*
• x* : indiquera une séquence quelconque de x qui peut être vide.
• x* = ou x ou xx ou xxx…
L4 = langage (x*)
Définition des langages
•Considérons le langage
L = {a,ab,abb,abbb,abbbb,…}
Toutes les chaînes constitués par un a suivi d’un nombre quelconque de b
On peut noter : L=Langage(ab*)
Langage dans lequel les mots sont la concaténation d’un a (a) initial avec un nombre quelconque
de b (b*).
Appliquons l’étoile de Kleene à toute la chaîne ab, on aura : (ab)*= ou ab ou abab ou ….
Définition des langages
Le langage définit par l’expression :
ab*a
Ensemble de toutes les chaînes de a et de b qui ont au moins deux lettres, qui commencent
et finissent par un a. et qui n’ont que des b ou rien à l’intérieur.
langage (ab*a)={aa,aba,abba,abbba,…}
Remarque :
◦ Fausse description : Ensemble de tous les mots qui commencent et puis finissent par a et qui n’ont que
des b (ou rien) entre eux.
◦ Le mot a appartient a cette description.
Définition des langages
Le langage définit par l’expression :
a*b*
Ensemble de toutes les chaînes de a et de b dans lesquelles les a’s viennent avant les b’s.
langage (a*b*)={ ,a,b,aa,bb,ab,bb,aaa,abb,…}
Remarque :
◦ a*b* (ab)*
◦ Le langage à droite contient abab tandis que celui à gauche ne le contient pas
Définition des langages
si r1 et r2 sont deux expressions régulières alors ;
• r1r2
• r1 r2
• r1*
Sont des expressions régulières
Exemple 1 :
={a,b}
L={w *| w contient la sous chaîne aa }
R = (a b)*aa (a b)*
Exemple 2 :
={a,b}
L={w *| w ne contient pas 3 b consécutifs }
R= (a ba bba)* ( b bb)
Définition des langages
Théorème :
◦ Un langage L est dit régulier si et seulement si il existe une expression régulière qui le génère.
Propriétés Étant donné deux langages réguliers L1 et L2
• L1 L2 : est un langage régulier
• L1 . L2 : est un langage régulier
• L1* : est un langage régulier
•L1 L2 = est un langage régulier
• LR : est un langage régulier
• L1\L2 : est un langage régulier
Définition des langages
Deux expressions régulières et sont dites équivalentes si L() = L() Autrement s’ils génèrent
le même langage
Exemple :
Langage de tous les mots qui ont au moins 2 a’s peut être décrit par l’expression régulière :
(a b)*a (a b)*a (a b)*
Autre expression régulière
b*ab*a(a b)*
On peut noter :
(a b)*a (a b)*a (a b)*= b*ab*a(a b)*
Exercice
Donner les expressions régulières qui génèrent les langages suivants:
L1 = {ω∈{a,b}*, tel que ω contient exactement bbb}
L2 = {ω∈{a,b}*, tel que ω contient la sous chaîne bbb}
L3 = {ω∈{a,b}*, tel que ω contient seulement 3b, le reste c'est des a's}
L4 = {ω∈{a,b}*, tel que ω contient un nombre de a divisible par 3}
L5 = {ω∈{a,b}*, tel que ω contient un nombre paire de a}
L6= {{ω∈{a,b}*, tel que ω ne contient pas 3b Consécultifs}
L6 = {ω∈{a,b}*, tel que ω contient un nombre impaire de b}
L7 = {ω∈{a,b}*, tel que ω contient la sous chaîne aaa ou la sous chaîne bbb mais pas les deux en
même temps}
Questions ?