Plan

1. La classification de Chomsky
2. Langages réguliers et expressions régulières
3. Règles avec parties droites vides dans les grammaires algébriques
4. Forme normale de Chomsky
5. Propriétés de fermeture
6. Non expressivité
7. Langages récursivement énumérables

Langage régulier (rationnel)

• Nombre impair de a et nombre impair de b

  A ® aB A ® bC

  B ® aA B ® bD B ® b

  C ® aD C ® bA C ® a

  D ® aC D ® bB

  
  Exemple de dérivation:
  

  A

  ® a B ® aa A ® aab C ® aaba D ® aabaa C ® aabaaa

Langage algébrique (context-free)

• langage { aⁿ bⁿ | n > 0 }
  

  S ® a S b

  S ® ab

  
  Exemple de dérivation:

  S

  ® a S b ® aa S bb ® aaa S bbb ® aaaabbbb

  
  
  
• système de parenthèses

  S ® a S b S

  S ® abS

  S ® aSb

  S ® ab

  
  Exemple de dérivation:

  S

  ® a S bS ® aa S bbS ® aaabbb S ® aaabbba S b ® aaabbbaabb

  
  
  
• automates à pile [Chomsky, Schutzenberger]
  On rajoute une pile au fonctionnement d'un automate fini
  Par exemple pour { a ⁿ bⁿ | n > 0 }. Table de transitions (q₁ état initial, Z dans la pile, F = { q₄ })
  

  	a,Z	a,X	b,X	e,Z
  q1	(q2, ZX)
  q2		(q2, XX)	(q3, e)
  q3			(q3, e)	(q4,Z)
  q4

Langage context-sensitive

• langage { a ⁿ bⁿ cⁿ | n > 0 }
  

  S ® e		S ® A
  A ® aABC		CB ® BC		aB ® ab		bC ® bc
  A ® aBC				bB ® bb		cC ® cc

  
  Exemple de dérivation:

  S		® A ® a A BC ® aa A BCBC ® aaaB CB CBC
  		® aaaBBC CB C ® aaaBB CB CC ® aa aB BBCCC
  		® aaa bB BCCC ® aaab bB CCC ® aaabb bC CC
  		® aaabbb cC C ® aaabbbc cC ® aaabbbccc

  
  Le contexte intervient; les dérivations ne font pas décroitre la taille des mots.

Langages et Grammaires

• S alphabet des symboles terminaux
• V_N ensemble de non terminaux, V = S È V_N
• S Î V_N axiome
• P ensemble fini de règles de productions de la forme a_i ® b_i (a_i Î V⁺ - S^*, b_i Î V^*)

Classification de Chomsky

• il peut figurer dans une règle S ® e
• alors il ne doit pas apparaître dans une partie droite de production.

Langage généré par une grammaire

• Une dérivation élémentaire ua v ¾® ub v s'obtient par application d'une règle a ® b de production.
  
  
• Une dérivation u ¾®^* v est une suite de dérivations élémentaires u=u₀ ¾® u₁ ¾® u₂ ... u_n=v (n ³ 0)
  
  
• Le langage généré par une grammaire G = (S, V_N, S, P) est:

  L(G) = { u | S

  * ¾®

  u Î S * }

• Un langage est de type i s'il existe une grammaire de type i qui le génère (0 £ i £ 3 ). Soit L_i les langages de type i sur S.
  
  
• Comme G de type i+1 implique G de type i, on a
  

  L3 Ì L2 Ì L1 Ì L0

  .
• { aⁿ bⁿ | n ³ 0 } Î L₂ -L₃
  
  
• { aⁿ bⁿ cⁿ | n ³ 0 } Î L₁ -L₂

Notations abrégées

• Souvent on factorise les productions qui ont une même partie gauche grâce au (méta)symbole | (barre verticale):

  		a ® b1 | b2 | ... bn
  pour
  		a ® b1 a ® b2 ... a ® bn

  
  
  
• Une autre notation fréquente est proche de la BNF (Backus Naur Form), la flèche est remplacé par ``::='':
  a ::= b₁ | b₂ | ... b_n
  
  
  
• Par exemple, l'espace des termes t est défini par
  t ::= t + t | t * t | t - t | t / t | nb
  qui ressemble à une définition récursive. Parfois on duplique les symboles non terminaux pour distinguer les occurences dans les parties droites:
  t,t' ::= t + t' | t * t' | t - t' | t / t' | nb

Langage régulier et automate fini

• Démonstration: Si G est la grammaire (de type 3) générant L, on considère l'automate non-déterministe A=(S, V_N, S, {q_f}, d) tel que
  
  B Î d(A, a) si A ® aB
  q_f Î d(A, a) si A ® a
  
  Alors T(A) = L(G).
  
  
• Réciproquement, si L=T(A) et A=(S, Q, q₀, F,d), on considère la grammaire G = (S, Q, q₀, P) telle que
  
  A ® aB si B Î d(A, a)
  A ® a si d(A,a) Ç F ¹ Ø
  
  Alors L(G) = T(A).

Expression régulière et automate (1/5)

• On admet l'équivalence entre automates finis avec ou sans e-transitions;
  
  
• on suppose que les automates finis n'ont qu'un seul état de fin q_f avec d(q_f,a) = Ø pour tout a Î S;
  
  
• de même, on suppose q₀ Ïd(q,a) pour tout qÎ Q et a ÎS;
  
  
  
  
  
• alors les automates finis reconnaissent les expressions régulières par les constructions suivantes.

Expression régulière et automate (2/5)

• [construction due à [Thompson] (l'inventeur du système Unix)]

Expression régulière et automate (3/5)

• Démonstration: Par la construction précédente, on montre par récurrence sur la taille de l'expression régulière que toute expression régulière est reconnue par un automate.
  
  
• Réciproquement, soit A=(S, Q, q₀, F) avec Q = {q₀, q₁, ... q_n-1}. Soit L_i,j^k l'ensemble des mots permettant d'aller de q_i à q_j en passant par des états q vérifiant < k. Alors

  Li,i0 = {e} È {a | d(qi, a) = qi }

  Li,j0 = {a | d(qi, a) = qj }

  Li,jk+1 = Li,jk È Li,kk (Lk,kk)* Lk,jk

  
  Et L=T(A) = È_{qiÎ F} L_0,iⁿ.

Expression régulière et automate (4/5)

Expression régulière et automate (5/5)

• L'automate obtenu par la construction précédente est non-déterministe, il a beaucoup de e-transitions.
  
  
• On peut toujours déterminiser l'automate obtenu, et considérer l'automate minimal.
  
  
• Il existe des constructions plus directes pour obtenir de bons automates (peut-être pas minimaux) [Glushkov; Brzozowski; Berry-Sethi; Berstel-Pin] en considérant les expressions régulières linéaires, et les expressions régulières dérivées.

Mot vide dans une grammaire algébrique

• Les productions A ® a doivent avoir une partie droite non vide (a ¹ e) à l'exception de l'axiome.
  
  
• Or, dans le cours 6, on avait par exemple autorisé
  

  S ® aSbS S ® e.

  
  
  
• Mais les deux définitions de grammaires algébriques génèrent les mêmes langages algébriques.
  
  En effet, si on a B ¾®^* e et une règle A ® a B b, on ajoute la règle A ® ab. Puis on supprime toutes les productions C ® e.
  Si on avait S ¾®^* e, on considère un nouvel axiome S' et on ajoute les nouvelles règles S' ® e et S' ® S.
  
  
• Sur l'exemple précédent, cela donne successivement
  

  S ® aSbS	S ® e	S ® abS	S ® aSb	S ® ab
  S' ® e	S' ® S	S ® aSbS	S ® abS	S ® aSb	S ® ab

Forme normale de Chomsky

• On trouve les non-terminales B et C telles que B ¾®^* C.
• Si on a A ® a B b avec C ® g et |g| ³ 2, on ajoute A ® agb.
• Puis on supprime les règles A ® B.
  
  
• A présent, les règles sont de la forme S ® e, A ® a, A ® a avec |a|³ 2.
  
  Pour chaque production A ® a= X₁X₂... X_n, on ajoute de nouvelles non-terminales Y_i et on pose
  • Y_i ® X_i quand X_i Î S
    
    
  • A ® X₁Y₂ Y₂ ® X₂Y₃ ...Y_n-1 ® X_n-1X_n.

Propriétés de clôtures (1/2)

• Un morphisme f est toute fonction de S dans S₁^* étendue sur les mots et sur les langages de manière naturelle:
  

  f(uv) = f(u)f(v) etf(L) = {f(w) | w Î L }

  
  
  
• Les langages réguliers sont clos par morphisme.
  
  
• Les langages algébriques sont clos par morphisme.
  
  
• Les langages réguliers forment une algèbre de Boole (clos par union, intersection et complément).
  
  
• Les langages algébriques sont clos par union;
  ils ne sont pas clos par intersection puisque:
  
  { aⁿ bⁿ cⁿ | n ³ 0 } = { aⁿ bⁿ c^* | n ³ 0 } Ç { a^* bⁿ cⁿ | n ³ 0 }

Propriétés de clôtures (2/2)

• Les langages algébriques sont clos par intersection avec un régulier: L algébrique, R régulier Þ L Ç R algébrique
  
  
• Démonstration:
  • G=(S,V_N,S,P) génère L;
    A = (S, Q, q₀, F) reconnait R;
    
    
  • la grammaire G' suivante génère L Ç R:
    
    G' = (S, V, S', P')
    
    V = { A_q,q' | A Î V_N  où  q,q' Î Q } È { S' }
    
    P' contient les règles productions suivantes:
    • ·A_q'0,q'n ® A_q'0,q'1¹ A_q'1,q'2² ··· A_q'n-1,q'nⁿ
      si A ® A¹ A² ··· Aⁿ est une production de P avec:
      Aⁱ Î V_N È S et d(q'_i-1, Aⁱ) = q'_i si Aⁱ Î S
      
      
    • ·S' ® S_q0,q avec q Î F
    
    

Non expressivité

• Lemme de l'étoile
  Si L est régulier, il existe n tel que:
  
  " wÎ L    |w| > n   Þ   w= uvx avec |v| > 0 et uvⁿx Î L pour tout n ³ 0.
  
  
  
  
  Exercice 4 Montrer que {aⁿbⁿ | n ³ 0} n'est pas régulier
  
  Exercice 5 Montrer que {aⁿbaⁿ | n ³ 0} n'est pas régulier
  
  
• Lemme de la pompe
  Si L est algébrique, il existe n tel que:
  
  " wÎ L    |w| > n   Þ   w= uvxyz avec |vy| > 0 et uvⁿxyⁿz Î L pour tout n ³ 0.
  
  
  
  
  Exercice 6 Montrer que {aⁿbⁿcⁿ | n ³ 0} n'est pas algébrique.

Langage récursivement énumérable

• Démonstration: D'abord si un langage est de type 0, on peut construire une machine de Turing qui le génère.
  
  
• Réciproquement, supposons qu'un langage L vérifie L=T(M) avec M = (Q, S, G, d, q₀,B, F) est une machine de Turing. On construit la grammaire G=(SÈ {$}, Q È G È {S,S'}, S, P) avec comme productions:
  
  qX ® Yp si (u,q,Xv) ¾® (uY,p,v)
  q$ ® Yp$ si (u,q,e) ¾® (uY,p,e)
  ZqX ® pZY si (uZ,q,Xv) ¾® (u,p,ZY)
  Zq$ ® pZY$ si (uZ,q,e) ¾® (u,p,ZY)
  S ® q₀S'
  S' ® a S'
  S' ® $
  
  Alors u$ Î L(G) ssi u Î T(M).

Quelques exercices

This document was translated from L^AT_EX by H^EV^EA.