Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

Notions de mots et de langage

 

Notions de mots et de 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.

Nous commençons par un ensemble fini et non vide \(\Sigma\) de symboles, appelé l'alphabet. A partir des symboles individuels, nous construisons des mots, qui sont des séquences finies de symboles de l'alphabet. Par exemple, si l'alphabet \(\Sigma = \{a, b\}\), alors abab et aaabbba sont des mots sur \(\Sigma\). A 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.

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, c'est-à-dire si

$$w = a_1a_2\dots a_n$$ et $$v = b_1b_2\dots b_n$$ 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_n$$

L'inverse d'un mot est obtenu en écrivant les symboles dans l'ordre inverse ; si w est un mot comme indiqué ci-dessus, alors son inverse \(w^R\) est $$w^R=a_n \dots a_2a_1$$

La longueur d'un mot w, notée \(|w|\), est le nombre de symboles dans ce mot. 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\). Les relations simples suivantes : $$|\lambda|=0$$ $$\lambda w = w\lambda = w$$ sont valables pour tout w.

Toute chaîne de symboles consécutifs dans un certain w est dite une sous-chaîne de w. Si $$w=vu$$ alors les sous-chaînes v et u sont respectivement un préfixe et un suffixe de w. Par exemple, si \(w = abbab\), alors \(\{\lambda, a, ab, abb, abba, abbab\}\) est l'ensemble de tous les préfixes de w, tandis que bab, ab, b sont certains de ses suffixes.

Les propriétés simples des mots, telles que leur longueur, sont très intuitives et nécessitent probablement peu d'explications. Par exemple, si u et v sont des mots, alors la longueur de leur concaténation est la somme des longueurs individuelles, c'est-à-dire, $$|uv|=|u|+|v|$$

Mais bien que cette relation soit évidente, il est utile de pouvoir la préciser et de la prouver. Les techniques pour le faire sont importantes dans des situations plus compliquées. (Voir la démonstration).

Si w est un mot, alors \(w^n\) représente le mot obtenu en répétant w n fois. Comme cas particulier, on définit : $$w^0=\lambda$$, pour tout w.

Si \(\Sigma\) est un alphabet, alors nous utilisons \(\Sigma^{*}\) pour désigner l'ensemble des mots obtenus en concaténant zéro ou plusieurs symboles de \(\Sigma\). L'ensemble \(\Sigma^{*}\) contient toujours \(\lambda\). Pour exclure le mot vide, nous définissons : $$\Sigma^{+}=\Sigma^{*} - \{\lambda\}$$.

On définitl'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.

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.

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

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

L'ensemble \(L=\{a^n b^n : n\ge0\}\) est aussi un langage sur \(\Sigma\). Les mots aabb et aaaabbbb sont dans le langage L, mais le mot abb n'est pas dans L. Ce langage est infini.

Puisque les langages sont des ensembles, l'union, l'intersection et la différence de deux langages sont immédiatement définies.

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 $$

L'inverse d'un langage est l'ensemble de tous les renversements de mots, c'est-à-dire : $$L^{R}=\{w^R : w \in L\}.$$

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\) ; Plus précisément, $$ L_1L_2=\{xy: x \in L_1, y \in L_2\}. $$

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.

Enfin, nous définissons la fermeture en étoile d'un langage L comme : $$L^{*}=L^0 \cup L^1 \cup L^2 \cup \dots $$, et la fermeture positive comme : $$L^{+}=L^1 \cup L^2 \cup \dots $$

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.