LES AUTOMATES ET LES LANGAGES
1°) Introduction
La communication entre les hommes a lieu dans des langages naturels.
Ces derniers peuvent être ambigus car le cerveau humain peut comprendre les subtilités de ces
langages, les non-dits...
Par contre la communication homme-machine doit se faire dans un langage artificiel non
ambigu.
Exemple : Voici un schéma qui représente les niveaux de langage intervenant en
programmation
PASCAL, CAML sont des langages compilés : tout le source du programme est d'abord analysé
lexicalement, syntaxiquement, sémantiquement, linké(ajout des librairies) puis traduit
complétement en p-code avant d'être exécuté.
BASIC est un langage interprété : les instructions sont traduites interactivement l'une après
l'autre en langage machine.
2°) Définitions des notions d'alphabet, de mot et de langage.
A - Notion d'alphabet
Un alphabet $A$ est un ensemble fini de symboles ou d'éléments appelé lettres ou caractères.
B - Notion de mot
Un mot est une suite finie d'éléments d'un alphabet A
Ex : le mot $u = u_1u_2.....u_n$ où $\forall i ∈ [|1,n|] \ u_i \in A$
Ce mot $u$ a une longueur $n$ que l'on note $|u| = n$
Soit $a$ un symbole de l'alphabet $A$ , une occurrence de $a$ dans le mot $u$ est un indice $i \in [|1 , |u |]$ tel que $a = u_i$. On note $|u|_a$ le nombre d'occurrences du symbole a dans le mot u.
Ex : $A = \{a ; b \} ; u = ababa ; |u| = 5 ; |u|_a = 3 ; |u|_b = 2$
l'ensemble des mots défini sur un alphabet $A$ se note $A^*$
La suite vide se note $\varepsilon$ ou $1_A$ et s'appelle le mot vide sa longueur est $0$
On note $A_0$ l'ensemble des mots de longueur $0$ donc $A_0 = \{\varepsilon\}$
$A_1$ = l'ensemble des mots ou chaînes de caractères de longueur $1$.
$A_2 = A_1 \times A_1 =$ l'ensemble des mots ou chaînes de caractères de longueur $2$
$\cdots$
$A_n = A_1 \times A_1 \times \cdots \times A_1$ l'ensemble des mots ou chaînes de caractères de longueur $n$
donc $A^* = A_0 \cup A_1 \cup A_2 \cdots \cup A_n \cup \cdots =\bigcup_{i \in N} A_i$
On note $A^+ = A_1 \cup A_2 \cdots \cup A_n \cup \cdots =\bigcup_{i \in N^*} A_i$ = l'ensemble des mots de longueur non nulle donc $A^+= A^*- \{ε\}$
C - L'opération de concaténation
On peut définir sur $A^*$ une loi de composition interne : la concaténation notée .
$\forall u = u_1u_2 \cdots u_n \in A^* \quad \forall v = v_1v_2 \cdots v_m \in A^*$
$u . v$ est le mot $u_1u_2 \cdots u_nv_1v_2 \cdots v_m$
Théorème 1 :
$(A^*, .)$ est un monoïde
démonstration :
. est une loi interne ; . est associative ; . admet un élément neutre dans pour . c'est $\varepsilon$
Théorème 2 :
Tout mot s'écrit de façon unique comme la concaténation de mots de longueur 1
D - Notions de préfixe ,de suffixe et de facteur d'un mot
On peut définir dans $A^*$ la relation suivante notée $\leq$ par
$\forall u \in A^* \quad \forall v \in A^* \quad u \leq v$
s'il existe un mot $w$ tel que $v = u . w$
( on dit alors que $u$ est un préfixe de $v$)
Théorème 3
$\leq$ est une relation d'ordre partiel dans $A^*$
démonstration :
- $\leq$ est réflexive car $\forall u \in A^* \quad u \leq u $ puisque $u = u \varepsilon$
- $\leq$ est antisymétrique car $\forall u \in A^* \quad \forall v \in A^* $ si l'on a $u \leq v$ et $v\leq u$ alors $\exists w_1 \in A^* \quad v = u.w_1$ et $\exists w_2 \in A^* \quad u = v.w_2$ donc $ v = v.w_2.w_1$ donc $w_1 = w_2 = \varepsilon$ à cause de la longueur de $v$. donc $u = v$.
- $\leq$ est transitive car $\forall u \in A^* \quad \forall v \in A^* \quad \forall w \in A^* $ si l'on a $u \leq v$ et $v\leq w$ alors $\exists w_1 \in A^* \quad v = u.w_1$ et $\exists w_2 \in A^* \quad w = v.w_2$ donc $w = u.w_1.w_2$ donc $u \leq w$
Cette relation est alors une relation d'ordre. Cet ordre est partiel car il existe des couples de mots $u$ et $v$ tels que $u$ n'est pas préfixe de $v$ et $v$ n'est pas préfixe de $u$.
Soit $u \in A^*$ et soit $v \in A^*$ on dit alors que $u$ est un suffixe de $v$ s'il existe un mot $w$ tel que $v = w . u$
Soit $u\in A^*$ et soit $v \in A^*$ on dit alors que $u$ est un facteur de $v$ s'il existe des mot $w$ et $t$ tels que $v = t . u . w$. Toutes les lettres de $u$ se retrouvent consécutivement dans $v$ et dans le même ordre.
- Un préfixe de $v$ est un facteur gauche de $v$ et un suffixe de $v$ est un facteur droit de $v$.
- Soit $u\in A^*$ et soit $v \in A^*$ on dit alors que $u$ est un sous-mot de $v$ lorsque les lettres de $u$ se retrouvent peu importe leur position dans celles de $v$.
- Attention, ne confondez pas facteur de $v$ et sous-mot de $v$.
- Si $u$ est un facteur de $v$ alors $u$ est un sous-mot de $v$ mais la réciproque est fausse.
Ex : $u = 0011$ est un facteur de $v = 0100110$. $101$ n'est ni préfixe, ni suffixe de $v$.
$u = 00000$ est un sous-mot de $v = 0100110101$ mais n'est pas un facteur de $v$
- On appelle miroir ou inverse ou transposé d'un mot $u =u_1u_2\cdots u_n$ le mot $u^t =u_n \cdots u_2u1$
E - La notion de langage
a) Définition
Un langage $L$ défini sur l'alphabet A est un sous-ensemble (ou une partie) de l'ensemble $A^*$ des mots
Un langage pourra être défini :
- soit en extension : on donne la liste de tous ses éléments
- soit encompréhension : on donne une propriété caractéristique
Un langage sera décrit par une grammaire qui permettra de construire une procédure effective appelée automate nous permettant de décider si un mot fait ou non partie d'unlangage.
Il y a plusieurs classes de langages correspondant à différentes classes de grammaires et d'automates.
Par exemple, les langages réguliers correspondant aux grammaires régulières et auxautomates d'états finis.
Ils sont fort utiles pour décrire les entités lexicales deslangages de programmation.
Les langages hors-contexte correspondent aux grammaires hors-contexte et aux automates à piles. Ils sont fort utiles pour décrire la syntaxe des langages de programmation.
b)Remarque :
Un langage $L \in \mathcal{P}(A^*)$. Or $\emptyset \subset A^*$ donc $\emptyset \in \mathcal{P}(A^*)$ donc $\emptyset$ est donc un langage n'ayant aucun mot.
Il ne faut pas le confondre avec {ε} ou {1_A}
c) Exemples :
Ex 1
Pour $A = {0 ; 1}$ alors $A^* = {0 ; 1}^*$ ; $L = {0^n1^n /n \in N}$ formé de la concaténation de n "zéros"suivis de n "un".
Par convention $0^01^0$ est le mot vide $\varepsilon$.
Ex 2
Pour $A = {0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 } \cup { E ; -; . }$
On peut alors créer en Pascal des mots qui seront appelés des réels.
Par exemple, $-65.3$ ou $127 E-3$ sont des réels.
d) Opérations sur les langages définis sur le même alphabet A :
- l'union $L_1 \cup L_2$ ou somme $L_1 + L_2 = { u \in A^*/ u \in L_1 \text{ ou } u \in L_2}$
- l'intersection $L_1 \cap L_2 = { u \in A^*/ u \in L_1 \text{ et } u \in L_2}$
- le complément de $L_1$ dans $A^* = c(L_1) = { u \in A^*/ u \notin L_1 }$
- la différence ensembliste de $L_1$ et de $L_2$ qui est ${ u \in A^*/ u \in L_1 \tetx{ et } u \notin L_2 }$
- la différence symétrique $L_1 \delta L_2$ ou somme $L_1 + L_2 = { u \in A^*/ u \in L_1 \text{ ou bien } u \in L_2}$
- la concaténation $L_1.L_2 = { w \in A^* / w = u. v où u \in L_1 \text{ et } v \in L_2}$
- le miroir ou le transposé ou l'inverse de $L = L^t = {u^t /u \in L}$
- $L^0 = {\varepsilon} ; L_1 = L ; L¨2 = L.L ; \cdots ; L^n = L.L \cdots L$ (n fois)
- $L^{< n} = L^0 \cup L^1 \cup L^2 \cdots L^{n - 1}$
- $L^{< 0} = \emptyset$
- $L^{\leq n} = L^0 \cup L^1 \cup L^2 \cdots L^{n - 1}$
Exemple : si $A ={a}$ alors $L^{\leq 3} = {\varepsilon,a,aa,aaa}$ - La fermeture itérative de $L$ ou la fermeture de Kleene de $L$ ou l'itéré de $L$ ou l'étoile de $L$ ou l'itération de $L = L^* = L_0 \cup L_1 \cup L_2 \cup \cdots \cup L_n \cup \cdots = \bigcup _{i\in N} L_i$ = l'ensemble des mots formés par une concaténation finie de mots de $L$.
- On note aussi $L^* = L_0 + L_1 + L_2 + \cdots L_N + \cdots$
$L^* \neq \emptyset$ car même si $L = \emptyset$ car $\emptyset^* = {ε} - $L^+= L*- {ε}$ = l'étoile stricte de $L$
- Si $u \in A^*$ et $L$ défini sur $A$ alors $u^{-1}L= {v∈A*/uv∈L}$ est le langage résiduel de $L$associé à $u$Description d'un langage
Un langage fini peut être décrit par l'énumération des mots qui le composent
Un langage infini peut être décrit par l'application d'opérations sur des langages plus
simples ou par un ensemble de règles qui forment une grammaire.
Certains langages infinis ne peuvent pas être définis par les 2 moyens précédents. On dit
alors qu'ils sont indécidables.
Une expression régulière sur un alphabet $A$ est une formule de longueur finie
correctement parenthésée utilisant uniquement les opérations :
- somme +
- concaténation .
- étoile *
ainsi que les langages $\emptyset , \{ε\}$ et $\{x\}$ où x est une lettre quelconque de A.
On notera $\{ε\} : ε$ et $\{x\} : x$ pour alléger les notations.
Un langage est dit régulier lorsqu'il peut être décrit par au moins une expression
régulière.
L'ensemble des langages réguliers sur A est stable pour les opérations d'union, deconcaténation et d'étoile. D'après le Théorèmede Kleene, il est aussi stable pour les opérations d'intersection et de complémentarité.