CHAPITRE 4 LANGAGES HORS

CONTEXTE

Dr. Moez HAMMAMI

PLAN
 Grammaires Hors contextes
 Définition
 Dérivation gauche
 Dérivation droite
 Arbre syntaxique
 Grammaires ambiguës
 Classification de chomsky
 Automates à pile
 Définition
 Langages reconnus par un automate à pile avec état d’acceptation
 Exemple D’automates à pile
INTRODUCTION PAR UN EXEMPLE
Soit le langage L décrit par l'expression régulière suivante:
a(a* b*)b
Un mot  peut avoir la forme a bbb...b b ou a aaa...a b
On peut dire que  a la forme aMb, il reste à décrire M
S  aMb
M  A M peut être une suite de a ou une suite de b
M B
A  aA décrit récursivement une suite de a
A 
B  bB décrit récursivement une suite de b
B 
DÉFINITION D'UNE GRAMMAIRE HORS
CONTEXTE
Première définition
une grammaire G est un quadruplet (VT,VN,R,S) où:
 VT est un ensemble fini de symboles terminaux
 VN est un ensemble fini de symboles non terminaux:
 S: Axiome (start symbol), toute dérivation commence par S.
 R: règles de production. R ( VN)(VTVN)*
 Dans l'exemple de l'introduction:
 VN = {S,M,A,B}.
 VT={a,b} ensemble des terminaux.
 S = Axiome, R={ S  aMb, M  A, M  B, A  aA, A  , B  bB, B  }
DÉFINITION D'UNE GRAMMAIRE HORS
CONTEXTE
deuxième définition
 une grammaire G est un quadruplet (V,,R,S) où:
 V est un ensemble fini de symboles terminaux et n on terminaux:
(alphabet globale)
  est l'alphabet des symboles terminaux
 V- ensemble des non terminaux
 S: Axiome (start symbol), toute dérivation commence par S.
 R: règles de production. R ( V-)V*
 Dans l'exemple de l'introduction:
 V = {S,M,A,B,a,b}.
 ={a,b} ensemble des terminaux.
 V-={S,M,A,B} ensemble des non terminaux.
 S = Axiome, R={ S  aMb, M  A, M  B, A  aA, A  , B  bB, B  }
DÉFINITION D'UNE DÉRIVATION
∗
  se dérive en  et on note: 𝜑  s'il existe une suite de mots 0, 1,.., n
de V* tels que:
  = 0
 = n
  i, 0 i <n, i  i+1

 Le langage engendré par la grammaire G est:

∗
 L(G) = {*, S }

 L est dit langage à contexte libre (CFL) s'il existe une grammaire G qui le
génère.
DÉRIVATION GAUCHE
  se dérive directement le plus à gauche en  et on note:  
𝑔
s'il existe des mots 1 *, 2  V* tels que:
  = 1 X 2
  = 1 W 2
 R contient une production X  W
∗
  se dérive le plus à gauche en  et on note   s'il existe une
𝑔
suite de mots 0, 1,.., n de V* tels que:  = 0, = n et  i, 0 i
<n, i i+1
𝑔
DÉRIVATION DROITE
  se dérive directement le plus à droite en  et on note:   s'il
𝑑
existe des mots 1 V* 2 *, tels que:
  = 1 X 2
  = 1 W 2
 R contient une production X  W
∗
  se dérive le plus à droite en  et on note   s'il existe une
𝑑
suite de mots 0, 1,.., n de V* tels que:  = 0, = n et  i, 0 i
<n, i i+1
𝑑
EXEMPLE DE DÉRIVATIONS
soit G =(V, ,R,S) avec
= {x1,x2,+,*,(,)}, V =   {E,T,F},S = E et R:
E  E+T
E T
T  T*F
T F
F  (E)
F  x1
F  x2
soit  = x1 *(x2+x1)
 Dérivation gauche
 E T T*F F*F x1*F x1*(E) x1*(E+T) x1*(T+T) x1*(F+T) x1*(x2+T)
𝑔 𝑔 𝑔 𝑔 𝑔 𝑔 𝑔 𝑔 𝑔 𝑔
x1*(x2+F) x1*(x2+x1)
𝑔

 Dérivation droite
 Pour la dérivation droite, c'est le non terminal le plus à droite qui est dérivé à chaque étape
 ET T*F T*(E) T*(E+T) T*(E+F) T*(E+x1) T*(T+x1) T*(F+x1) T*(x2+x1)
𝑑 𝑑 𝑑 𝑑 𝑑 𝑑 𝑑 𝑑
F*(x2+x1) x1*(x2+x1)
𝑑 𝑑
ARBRE SYNTAXIQUE
 soit une grammaire G(V, ,R,S), un arbre syntaxique pour un mot  engendré par G
est un arbre dont:
 La racine est étiquetée par l'axiome S
 Les feuilles sont étiquetées par {}
 Les nœuds internes le sont par des éléments de V-
 Un nœud interne étiqueté B a des fils, de gauche à droite, étiquetés 1,2,..,n s'il
existe une production de R: B  12..n
  est formé de la concaténation des feuilles lues dans un parcours suffixe (profondeur
d'abord, gauche droite)

Exemple: arbre syntaxique pour x1*(x2+x1)

T
T * F
F ( E )
x1 E + T
T F
F x1
x2
GRAMMAIRES AMBIGUËS
 Une grammaire G est dite ambiguë s'il existe un mot   * possédant plus qu'un arbre
syntaxique.
 Une grammaire G est dite ambiguë s'il existe un mot   * ayant plus d'une dérivation gauche
 Une grammaire G est dite ambiguë s'il existe un mot   * ayant plus d'une dérivation droite
 Exemple:
 G(V, ,R,E)
 ={x1,x2,+,*,(,)}
 V-= {E} et R définit par:
 E  E+E
 E E*E
 E  (E)
 E  x1
 E  x2
 soit = x1+x1*x2
 Cette grammaire est ambiguë car la chaîne  a plus d'une dérivation gauche. en effet:

 E 𝑔
E+E 𝑔
x1+E 𝑔 x1 +E*E 𝑔
x1+x1*E 𝑔 x1+x1*x2 E E

E + E E * E
 E 𝑔 E*E 𝑔 E+E*E 𝑔 x1+E*E 𝑔 x1+x1*E 𝑔 x1+x1*x2
 de même on peut trouver deux dérivations droites x1 E * E  E + E x2
x1 x2 x1 x1
CLASSIFICATION DE CHOMSKY
Chomsky a établi une classification des langages par types de grammaires. Il a ainsi établi quatre
types de grammaires: type0, type1, type2 et type3. Selon Chomsky toute grammaire générant un
langage formel est de type 0. Pour définir les autres types de grammaires, il introduit des restrictions
de plus en plus sévères sur les règles de production.
Grammaires contextuelles « context-sensitive » ou de type 1(CG)
Une grammaire est contextuelle si toute règle de production :
αβ
α peut s’écrire θ A 
β Peut s’écrire θ’Ψ ’
Avec θ, , θ’, ’ dans V* (suite de terminaux ou non terminaux)
A dans Vn (non terminal)
Ψ Dans V* (suite non vide de terminaux ou non terminaux)
On voit que le symbole A de Vn qui se trouve dans α précédé par θ et suivi par  (dans le contexte θ
et  ) peut être substitué par Ψ et précédé par θ’ et suivi par ’ (d’où le nom «contextuelle»).
Exemple:
aBab
B est substitué par b que si elle est précédée par a.
CLASSIFICATION DE CHOMSKY
Grammaires non contextuelles « context-free » ou de type 2 (CFG)
Les productions dans ce cas sont de même forme que les CG mais avec une nouvelle contrainte telle
que :
θ =  = ε et θ’ = ’ = ε
Ainsi toutes les productions sont de la forme :
A β
Avec A  Vn (non terminal)
et B V* (suite non vide de terminaux et de non terminaux )
Le symbole A de Vn est substitué par β sans restriction de contexte
Exemple : Soit G une grammaire définie par :
G= {Vn ,Vt ,P,S}
Avec Vn = {S ,A,B} et Vt={a,b}
P: S aB|bA
A a|aS|bAA
Bb|bS|aBB
G est une grammaire hors contexte; toutes les productions de G ont un seul élément de Vn à
gauche.
CLASSIFICATION DE CHOMSKY
Grammaires Régulières ou de type3 :RG
C'est une grammaire Hors contexte, on impose en plus la contrainte suivante :
toutes les productions sont de la forme : A β
avec β = a ou β =aB ou β =ε
avec a dans Vt et B dans Vn
Exemple : Soit G une grammaire définie par:
G={Vn, Vt, P, S}
avec Vn= {S,A ,B} et Vt={0,1}
Les productions de P sont:
S 0A | 1B | 0
A  0A | 0S |1B
B 1B|1 | 0
Toutes les productions ont un élément de Vn à gauche et un élément de Vt suivi ou non par un
élément de Vn à droite. Donc c’est une grammaire régulière.
CLASSIFICATION DES LANGAGES
FORMELS
 Un langage contextuel ou de type 1 est un langage généré par une grammaire contextuelle.
 Un langage non contextuel ou de type 2 est un langage généré par une grammaire non
contextuelle.
 Un langage régulier ou de type 3 est un langage généré par une grammaire régulière .
 Soient F0,F1,F2,F3 les familles de langages de types 0 ,type1,type2 et type3 respectives alors F 3 
F2  F1  F0
AUTOMATES À PILE
 Introduction
 Par analogie avec les expressions régulières qui engendrent les langages réguliers, les grammaires
hors contextes engendrent les langages hors contexte. Aussi par analogie avec automates à états
finis qui reconnaissent les langages réguliers, les automates à pile reconnaissent les langages hors
contextes.
 Exemple: Utilisation d'un automate à pile
 L'automate à pile va tenter de lire le mot aaabbb pour vérifier s'il appartient ou pas à L = { 
{a,b}*,  = anbn n  0} qui n'est pas régulier sinon on aurait utilisé un DFA.
 Le PDA empile un X à la lecture d'un a et dès la lecture du premier b il commence à dépiler à la
rencontre de chaque b. Il accepte le mot quand la pile devient vide.
AUTOMATES À PILE
 Exemple: Utilisation d'un automate à pile
AUTOMATES À PILE
Exemple: Utilisation d'un automate à pile
DÉFINITION D'UN AUTOMATE À PILE
Un automate à pile non déterministe est un septuple (Q, ,,,q0, z, F) où:
Q : ensemble fini d'états
 : alphabet fini des symboles d'entrée
 : alphabet fini des symboles de pile
 : ensemble des règles de transition
q0 : état initial
z : symbole de pile vide
F : ensemble des états d'acceptation
 Définition d'une transition
Une règle de transition (q, , q',) considère:
 L'état courant q de l'automate
 Le caractère lu  sur le ruban (ou peut être )
 Le symbole  de sommet de pile (ou peut être z ou )
 une règle de transition indique :
 Le prochain état q' de l'automate
 La suite de symboles  à empiler à la place du sommet de la pile ou dans la pile vide
 La relation de transition  est l'ensemble des règles de transition vues comme
des quintuples   (Q  ( {})  (  {}))  (Q  *)
(q, , q',): on est à l'état q avec  en sommet de pile, on peut lire  du restant
à lire, remplacer  par  et transiter à l'état q'.
LANGAGES RECONNUS PAR UN PDA (AVEC
ÉTAT D’ACCEPTATION)

 Définitions: soit A(Q, ,,,q0, z, F) un PDA

 On appelle configuration initiale d'un PDA, le triplet (q0, ,z), avec  la chaîne
à reconnaître par le PDA.
 On appelle configuration finale d'un PDA, le triplet (qF, , ) avec qF F et  
*.
 Une configuration est un triplet (q:état courant , x:restant à lire,:contenu de la
pile).
 Remarques:
 si  = , la pile est vide.
 La succession des configurations se fait à travers , noté ↣.
 Le langage reconnu par un PDA est l'ensemble des mots lus à partir de la
configuration initiale jusqu'à l'obtention d'une configuration finale.
 Formellement
∗
 L(A) = {*/ (q0, ,z) (qF, , ) avec qF  F et   *}
↣
 Remarque:
 Pour la configuration finale d'un PDA, le contenu de la pile importe peu.
Cependant, un cas particulier est de considérer une configuration finale où la
pile serait alors vide. L'automate est dit alors automate à pile vide.
EXEMPLE D’AUTOMATES À PILE
 soit le langage à contexte libre L ={anbn, n  0}.
 Déterminons le PDA qui reconnaît L. Le principe étant d'empiler X à chaque rencontre d'un a, et
de dépiler un X au fur et à mesure de la lecture des b: A est donc
 A (Q,,,,q0, #, F)
 Q = {q0,q1,q2,q3}; = {a,b};  = {X,#}; F = {q3};  définie par

(q0,a,#) = (q1,X#) On a empilé X et on reste à q0 qui va faire une

boucle d'empilement.
(q0,a,X) = (q0,XX)
(q0,b,X) = (q1,) On dépile X et on se déplace à q1 qui va avoir une
boucle de dépilement
(q1,b,X) = (q1, ) dépilement successif de tous les X
(q1,,#) = (q2,#) état final q2 atteint

 Remarque: si n= 0 (L), il faut donc ajouter l'instruction (q0,,#) = (q2,#)

 Diagramme de transition équivalent

a,#X#
a,X XX b,X  b,X  ,# #

q0 q1 q2

,# #
EXEMPLE D’AUTOMATES À PILE
 Diagramme de transition équivalent

a,#X#
a,X XX b,X  b,X  ,# #

q0 q1 q2

,# #

 Trace d’exécution sur aabb

 (q0,aabb, #) ↣ (q0,abb,X#) ↣ (q0, bb,XX#) ↣ (q1,b,X#) ↣ (q1, , #) ↣ (q2, , #)
 Trace d’exécution sur abb
 (q0,aab, #) ↣ (q0,bb,X#) ↣ (q1,b,#) ↣ (q2, b, #) 𝑏𝑙𝑜𝑐𝑎𝑔𝑒 𝑠𝑎𝑛𝑠 𝑡𝑒𝑟𝑚𝑖𝑛𝑒𝑟 𝑙𝑎 𝑐ℎ𝑎𝑖𝑛𝑒 chaine refusée
 Trace d’exécution sur aab
 (q0,aab, #) ↣ (q0,ab,X#) ↣ (q0, b,XX#) ↣ (q1,  ,X#) 𝑏𝑙𝑜𝑐𝑎𝑔𝑒 𝑑𝑎𝑛𝑠 𝑢𝑛 é𝑡𝑎𝑡 𝑑𝑒 𝑟𝑒𝑓𝑢𝑠 chaine refusée