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 x1.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 x1 2 nw=′w ⇔   x = x ∀k ∈ 1,nw = x x x ′  ′ 1′ 2′ n′ k k [] 1.4.1 Approche de la notion : Opération de base sur ...