Introduction aux langages formels : Notions de mots et de langage

Introduction aux langages formels

Qu'est-ce qu'un langage ?

Nous sommes tous familiers avec la notion de langues naturelles, telles que l'arabe, l'anglais et le français. Pourtant, la plupart d'entre nous trouveraient probablement difficile de dire exactement ce que signifie le mot "langue". Les dictionnaires définissent le terme de manière informelle comme un système adapté à l'expression de certaines idées, de certains faits ou concepts, y compris un ensemble de symboles et de règles pour leur manipulation.

Bien que cela nous donne une idée intuitive de ce qu'est un langage, ce n'est pas une définition suffisante pour l'étude des langages formels. Nous avons besoin d'une définition précise de ce terme.

Alphabet et mots

Nous commençons par un ensemble fini et non vide \(\Sigma\) de symboles, appelé l'alphabet. À partir des symboles individuels, nous construisons des mots, qui sont des séquences finies de symboles de l'alphabet.

Définition - Alphabet et mot

Un alphabet \(\Sigma\) est un ensemble fini et non vide de symboles.
Un mot sur \(\Sigma\) est une séquence finie de symboles de \(\Sigma\).

Exemple

Si l'alphabet \(\Sigma = \{a, b\}\), alors abab et aaabbba sont des mots sur \(\Sigma\).

À quelques exceptions près, nous utiliserons les lettres minuscules a, b, c, ... pour les éléments de \(\Sigma\) et u, v, w, ... pour les mots. Nous écrirons, par exemple : \[ w = abaaa \] pour indiquer que le mot w a la valeur spécifique abaaa.

Opérations sur les mots

Concaténation

La concaténation de deux mots w et v est le mot obtenu en ajoutant les symboles de v à l'extrémité droite de w.

Définition - Concaténation Si \(w = a_1a_2\dots a_n\) et \(v = b_1b_2\dots b_m\), alors la concaténation de w et v, désignée par \(wv\), est : \[ wv = a_1a_2\dots a_nb_1b_2\dots b_m \]

Inverse

L'inverse d'un mot est obtenu en écrivant les symboles dans l'ordre inverse.

Définition - Inverse Si \(w = a_1a_2\dots a_n\), alors son inverse \(w^R\) est : \[ w^R = a_n \dots a_2a_1 \]

Longueur

La longueur d'un mot w, notée \(|w|\), est le nombre de symboles dans ce mot.

Définition - Longueur Pour un mot \(w = a_1a_2\dots a_n\), \(|w| = n\).

Mot vide

Nous aurons souvent besoin de nous référer au mot vide, qui est une chaîne sans aucun symbole. Elle sera dénotée par \(\lambda\).

Propriétés du mot vide \[ |\lambda| = 0 \] \[ \lambda w = w\lambda = w \quad \text{pour tout mot } w \]

Préfixe, suffixe et sous-chaîne

Toute chaîne de symboles consécutifs dans un certain w est dite une sous-chaîne de w.

Définition - Préfixe et suffixe Si \(w = vu\), alors les sous-chaînes v et u sont respectivement un préfixe et un suffixe de w.

Exemple

Si \(w = abbab\), alors :

L'ensemble de tous les préfixes de w est : \(\{\lambda, a, ab, abb, abba, abbab\}\)
Quelques suffixes de w sont : bab, ab, b

Puissance d'un mot

Si w est un mot, alors \(w^n\) représente le mot obtenu en répétant w n fois.

Définition - Puissance d'un mot \[ w^n = \underbrace{ww\dots w}_{n \text{ fois}} \] Comme cas particulier, on définit \(w^0 = \lambda\) pour tout w.

Propriété fondamentale : longueur de la concaténation

Proposition Si u et v sont des mots, alors la longueur de leur concaténation est la somme des longueurs individuelles : \[ |uv| = |u| + |v| \]

Bien que cette relation soit évidente, il est utile de pouvoir la préciser et la prouver. Les techniques pour le faire sont importantes dans des situations plus compliquées.

Démonstration

Voir la démonstration complète

Ensembles de mots

Fermeture de Kleene \(\Sigma^{*}\)

Définition - \(\Sigma^{*}\) Si \(\Sigma\) est un alphabet, alors \(\Sigma^{*}\) désigne l'ensemble des mots obtenus en concaténant zéro ou plusieurs symboles de \(\Sigma\).

L'ensemble \(\Sigma^{*}\) contient toujours \(\lambda\).

Ensemble des mots non vides \(\Sigma^{+}\)

Définition - \(\Sigma^{+}\) Pour exclure le mot vide, nous définissons : \[ \Sigma^{+} = \Sigma^{*} - \{\lambda\} \]

On définit l'ensemble \(\Sigma^{+}\) des mots non vides sur \(\Sigma\) comme le plus petit ensemble tel que :

Pour toute lettre (symbole) a de \(\Sigma\), \(a \in \Sigma^{+}\)
Pour tous \(u \in \Sigma^{+}\) et \(a \in \Sigma\), \(ua \in \Sigma^{+}\)

Où \(ua\) représente la concaténation du mot u et de la lettre a.

Remarque importante Alors que \(\Sigma\) est fini par hypothèse, \(\Sigma^{*}\) et \(\Sigma^{+}\) sont toujours infinis puisqu'il n'y a pas de limite à la longueur des mots dans ces ensembles.

Définition d'un langage

Définition - Langage Un langage est défini très généralement comme un sous-ensemble de \(\Sigma^{*}\).

Cette définition est assez large ; tout ensemble de mots sur un alphabet \(\Sigma\) peut être considéré comme un langage.

Exemple 1 : Langage fini

Soit \(\Sigma = \{a, b\}\), alors :

\[ \Sigma^{*} = \{\lambda, a, b, aa, ab, ba, bb, aaa, aab, \dots \} \]

L'ensemble \(L = \{a, aa, aab\}\) est un langage sur \(\Sigma\). Parce qu'il a un nombre fini de mots, nous l'appelons un langage fini.

Exemple 2 : Langage infini

L'ensemble \(L = \{a^n b^n : n \ge 0\}\) est aussi un langage sur \(\Sigma\).

Les mots aabb (\(a^2b^2\)) et aaaabbbb (\(a^4b^4\)) sont dans le langage L.
Le mot abb n'est pas dans L.

Ce langage est infini.

Opérations sur les langages

Puisque les langages sont des ensembles, les opérations ensemblistes classiques s'appliquent.

Opérations ensemblistes

Union : \(L_1 \cup L_2 = \{w : w \in L_1 \text{ ou } w \in L_2\}\)
Intersection : \(L_1 \cap L_2 = \{w : w \in L_1 \text{ et } w \in L_2\}\)
Différence : \(L_1 - L_2 = \{w : w \in L_1 \text{ et } w \notin L_2\}\)

Complément

Définition - Complément Le complément d'un langage est défini par rapport à \(\Sigma^{*}\) ; c'est-à-dire que le complément de L est : \[ \bar{L} = \Sigma^{*} - L \]

Inverse

Définition - Inverse d'un langage L'inverse d'un langage est l'ensemble de tous les renversements de mots : \[ L^{R} = \{w^R : w \in L\} \]

Concaténation

Définition - Concaténation de langages La concaténation de deux langues \(L_1\) et \(L_2\) est l'ensemble de tous les mots obtenus en concaténant n'importe quel élément de \(L_1\) avec n'importe quel élément de \(L_2\) : \[ L_1L_2 = \{xy : x \in L_1, y \in L_2\} \]

Puissance d'un langage

Définition - Puissance d'un langage On définit \(L^n\) comme L concaténé avec lui-même n fois, avec les cas particuliers : \[ L^0 = \{\lambda\} \] \[ L^1 = L \] pour chaque langage L.

Fermetures

Définition - Fermeture étoile (Kleene star) La fermeture en étoile d'un langage L est : \[ L^{*} = L^0 \cup L^1 \cup L^2 \cup \dots \]

Définition - Fermeture positive La fermeture positive d'un langage L est : \[ L^{+} = L^1 \cup L^2 \cup \dots \]

Remarque On a la relation : \(L^{*} = L^{+} \cup \{\lambda\}\)

Exemples d'opérations

Soit \(\Sigma = \{a, b\}\), et considérons les langages :

\(L_1 = \{a, ab\}\)
\(L_2 = \{b, ba\}\)

Alors :

\(L_1L_2 = \{ab, aba, abb, abba\}\)
\(L_1^2 = \{aa, aab, aba, abab\}\)
\(L_1^{*}\) contient \(\lambda\), a, ab, aa, aab, aba, abab, ... (toutes les concaténations possibles de a et ab)

Tableau récapitulatif des notations

Notation	Signification	Exemple (\(\Sigma=\{a,b\}\))
\(\Sigma\)	Alphabet (ensemble fini de symboles)	\(\{a, b\}\)
\(w\)	Mot (séquence finie de symboles)	\(abba\)
\(\lambda\)	Mot vide	\(\| \lambda \| = 0\)
\(\|w\|\)	Longueur d'un mot	\(\|abba\| = 4\)
\(w^R\)	Inverse d'un mot	\((abba)^R = abba\)
\(\Sigma^{*}\)	Tous les mots sur \(\Sigma\) (y compris \(\lambda\))	\(\{\lambda, a, b, aa, ab, ba, bb, \dots\}\)
\(\Sigma^{+}\)	Tous les mots non vides sur \(\Sigma\)	\(\{a, b, aa, ab, ba, bb, \dots\}\)
\(L \subseteq \Sigma^{*}\)	Langage (ensemble de mots)	\(L = \{a^n b^n : n \ge 0\}\)
\(L_1L_2\)	Concaténation de langages	\(\{a\}\{b\} = \{ab\}\)
\(L^n\)	Puissance d'un langage	\(L^2 = LL\)
\(L^{*}\)	Fermeture étoile	\(L^0 \cup L^1 \cup L^2 \cup \dots\)
\(L^{+}\)	Fermeture positive	\(L^1 \cup L^2 \cup \dots\)

Résumé du cours

Ce cours introduit les concepts fondamentaux de la théorie des langages formels :

Alphabet (\(\Sigma\)) : ensemble fini de symboles
Mot : séquence finie de symboles
Opérations sur les mots : concaténation, inverse, longueur, puissance
Ensembles de mots : \(\Sigma^{*}\) (tous les mots), \(\Sigma^{+}\) (mots non vides)
Langage : sous-ensemble de \(\Sigma^{*}\)
Opérations sur les langages : union, intersection, complément, concaténation, fermetures étoile et positive

Mots-clés : #Alphabet #Mot #Langage #Concaténation #FermetureDeKleene #ThéorieDesLangages

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Introduction aux langages formels : Notions de mots et de langage