Cours-ThL1

1.3.2 Facteurs d'une chaîne
1. ALPHABETS et LANGAGES

o Facteur gauche (ou préfixe) : Toute chaîne obtenue en supprimant un
1.1 DÉFINITION D'UN ALPHABET nombre quelconque (éventuellement nul) de symboles en fin de chaîne.
Un alphabet X est un ensemble fini de symboles ou de caractères.
o Facteur droit (ou suffixe) : Toute chaîne obmant un

nombre quellement nul) de symboles en début de chaîne.
1.2 LES CHAÎNES
o Facteur (ou sous-chaîne) : Toute chaîne obtenue en supprimant un préfixe
w = x x x
1.2.0 Définition une chaîne ( 1 2 n ) est un n-uplet d'éléments appar-

et un suffixe.
tenant à un alphabet donné. Pour faciliter les écritures, w sera notée x1x2 xn

o préfixe, suffixe, sous-chaîne propre de w : Toute chaîne x non vide

respectivement préfixe, suffixe, sous-chaîne de w et telle que x ≠ w .
1.2.1 Longueur d'une chaîne : c'est le nombre de symboles qui la composent

Siw x x x long w w n
= 1 2 n () = =



1.4 NOTION DE LANGAGE
1.2.2 Cas particulier : la chaîne vide

w long 0
=() =
ε ()
ε =
ε =
1.4.0 Définition d'un langage :

De façon générale, on appelle langage un ensemble de conventions permettant

de conceptualiser la pensée et d'échanger avec d'autres interlocuteurs à l'aide d'un
1.2.3 Égalité de deux chaînes:
support comme la parole, l'écriture, etc.

w=′w = n

w = x x x
1 2 n
w=′w ⇔


x = x ∀k ∈ 1,n
w = x x x ′
 ′ 1′ 2′ n′ k k []


1.4.1 Approche de la notion :


Opération de base sur les chaînes : la concaténation
1.3 OPÉRATIONS SUR LES CHAÎNES Cf. produit cartésien de 2 ensembles et produit par concaténation
On considère l'ensemble L des chaînes construites à partir d'un alphabet X
2
X X. X w | w x|x , xetx X
Soit un alphabet X, = ={}= ′ ′ ∈

k
1.3.0 La concaténation : La concaténation de deux chaînes w et w ′ est
X =()x x x , x ∈X ,∀i ∈ 1, k
{ [] }
1 i k i

l'opération qui consiste à juxtaposer les éléments de à la suite de ceux de .
w ′ w
k k −1 k −1 k−1 X =X.X =XX =X X
w = x x w ′ =′x x ′
1 n 1 p
+ k 2 k
X = X =X X .... X ...


w w ww x x x x
|| ′ = ′ = 1 n 1′ p′
k >0


* + 0 + k 0
X ={}
ε X = X X = X avec par convention X ={
ε}

1.3.1 Propriétés :
{}
ε ≠
ε ≠∅
k≥0


∗
o opération interne
Sur X la concaténation notée || est une opération
o ww ′ = w+′w
− interne 

∗ 
⇒ −
 X ,|| est un demi groupe ∗
o associativité ∀ww ′ w ′ , ww ′ w ′ = w()w ′ w ′ ′ =()ww ′ w ′ ′
⇒
ε
 X ,||, monoïde libresur X
− associative


−
ε
dotée d' un élément neutre

o élément neutre : ∃
ε |∀w
εw = w
ε = w



1.4.2 Définition d'un langage formel :
1.3.1 Occurrences d'un symbole :

w est l'opération qui extraie les occurrences du symbole a dans la chaîne w .
a
Un langage formel construit à l'aide d'un vocabulaire X est un sous-ensemble du

∗ ∗ ∗
X X L X
monoïde libre Langage L sur : ⊆
Exemple : X = a,b, e, n w = banane w =6w= 2, 4 w = 3, 5
{} {} { }
a n




 
n n
= = ∀ ≥ = ∀ ≥ Exemples : ={} ={}
exemple : X a,b L a b , n 1  aaaabbbb , n 1 L A,, Z, a,, z C 0,,9
{}{}

 
n fois n fois


L C ensemble des chiffres et des lettres


Note : X est un ensemble fini. L peut-être fini ou infini
ensemble des chaînes formées d'une lettre suivie d'un chiffre
LC


4
ensembleînes de quatre lettres
L

Un langage est dit formel s'il fait appel à un alphabet X et si toute expression
∗
ensemble des chaînes d'un nombre quelconque de lettres
L
∗
de ce langage s'exprime par une chaîne appartenant au monoïde X
∗
≥
ensemble des chaînes de longueur 1, composées indifféremment de
LL C
( )


lettres ou de chiffres mais commençant forcément par une lettre
1.5 OPÉRATIONS DE BASE SUR LES LANGAGES
+
1
ensemble des chaînes de longueur ≥ , composées de chiffres
C



*
X ensemble fini, monoïde libre sur X
X


∗ ∗
Soient 2 langages (formels) A et B construits sur X . Par définition, A ⊆ X et B ⊆ X
2. GRAMMAIRES


Les opérations sur les langages peuvent se définir au sens ensembliste.
(Cf. Définition d'un ensemble en extension, en compréhension)

V
Par définition, un langage formel construit à l'aide du vocabulaire T est un sous-
L'union des deux langages A et B, est le langage constitué par les chaînes
∗
V
appartenant au langage A ou au langage B. ensemble du monoïde T .
L'intersection des deux langages A et B, est le langage constitué par les chaînes

∗
appart et. V ={}0,1 V = w = xx , x = 0 ou1 ∀i ∈ 1,n ∀n ∈NL ={}01,0, 001,10
{}[]
1
T T n i
Exemple :


* *
A = X − A = w
ε X et w ∉ A
{ }
Complément de A :
Exemple 2:

 
*
F = a, , z, A Z, â, à, é,è,ê, ë,î,ï,û, ù, ü,ô, ö,:.;,!?"
 
AB = w
ε X ∃ x ∈A ∃ y ∈B w = xy
Concaténation de deux langages : { | , , }


 
lettresdiacritées ponctuation




∗
Sur le monoïde libre F construit à partir de l'alphabet F, on peut définir le langage
3
 X =
ε, a, b A =
ε, ab,ba B = a, b, b
{}{} { }
Exemple1 :
d'un auteur comme Gérard de Nerval par exemple en listant l'ensemble des chaînes
3 2 4 2 3

présentes dans les ouvrages que nous a laissés le poète :
AB = a, b, b , aba, ab , ab ,ba ,bab, bab




L( Nerval) = Les filles du feu Aurélia Les Illumi nés Le Voyage en Orient




Pour Victor Hugo, cela serait plus difficile.

X = a, b, c A = a, ab B = c,bc
{}{} { }
Exemple 2 :

 2
AB = ac, abc, ab c AB ≤ A × B Si le langage est infini, la définition extensive du langage devient impossible. Il est


nécessaire d'avoir recours à une définition en compréhension.



2.1 BUT : Trouver un moyen de spécifier un langage avec une intention double.


Fermeture de Kleene de A ("Iterate", itération en français) :
o génération un nombre fini de règles permet de générer le langage
* k k
A = A = w|w ∈ A ,∀k ∈ N
{ }
o reconnaissance méthode pour dire si une chaîne bâtie sur le monoïde appartient
≥
k 0

ou non au langage donné. En fait, on demande à une grammaire plus que cela.



Un langage peut être caractérisé selon plusieurs façons suivantes. Voyons en deux :



2.1.1 Propriété commune à tous les éléments d'un langage :


n n
3.1 RÈGLE CONTEXTUELLE :
={} = ∀ ≥
Par exemple : X a, b L { a b , n 1}

Une règle est contextuelle si sa partie gauche productive A est de longueur

égale à 1 A = 1, et si elle est de la forme :
2.1.2 Axiomatique formelle : (même exemple) Si S ∈L, alors aSb ∈L
+ *
On voudrait que ce système formel soit le plus proche possible d'une procédure 
C ∈()V V et C ∈()V V

g N T d N T


C AC → C BC avec ou
g d g d 

∗ +
X Y
 C V V et C V V
∈ ∈
d N T g N T
2.2 DÉFINITION FORMELLE D'UNE GRAMMAIRE SYNTAGMATIQUE :




Une grammaire syntagmatique (Phrase Structure Grammar) G est définie par un
3.2 RÈGLE NON CONTEXTUELLE :
quadruplet =
G V , V , P, S
N T
Une règle est non contextuelle si les contextes gauches et droits sont vides et la

longueur de sa partie gauche est égale à 1, c.à.d. si elle est de la forme :
∗
o V : Vocabulaire non terminal ou vocabulaire auxiliaire (ensemble fini de
N
A r avec A V et r V V
→ ∈ ∈() Note : A =1 puisque A∈VN
N N T

symboles ou de variables). Métalangage servant à spécifier le langage