Calculabilité - Décidabilité (LI347) [0.3cm] Cours no5

Stef Graillat

Description

Calculabilité - Décidabilité (LI347)oCours n 5Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚5) 1 / 36Résumé du cours précédentPropriété de fermeture des langages réguliers : union, intersection,complémentaire, différence, fermeture, concaténation, renversementCoûts des conversions entre les représentations : AFD, AFN, ε-AFN,ERPropriété de décision des langages réguliers : tester si un langage estvide, si un mot appartient à un langage, si deux langages sont égauxMinimisation d’un automate : un automate reconnaissant le mêmelangage mais avec le moins d’états possibles (unicité de l’automateminimal)S. Graillat (Univ. Paris 6) LI347 (cours n˚5) 2 / 36Partie II :Automates à piles, grammaireshors-contexte et langageshors-contexteS. Graillat (Univ. Paris 6) LI347 (cours n˚5) 3 / 36Grammaires et langages hors-contexteDéfinition d’un ensemble de langage contenant strictement les langagesréguliers.Notation récursive naturelle (les grammaires)Rôle central dans les années 60 pour la compilationCompilation, Parsers, XMLModèle plus puissant, Automates à pile.S. Graillat (Univ. Paris 6) LI347 (cours n˚5) 4 / 36Grammaires hors-contexte∗ RLangage défini par les palindromes L ={w ∈Σ : w = w }palPar exemple otto ∈ L , laval ∈ Lpal palPosons Σ ={0,1}Application du lemme de pompage : L n’est pas régulier!paln nSoit n donné par le lemme de pompage, regarder 0 10 .Définition récursive du langage :Base : ε, 0 ...

Informations

• Publié par: Omkou
• Nombre de lectures: 65
• Langue: Français

Extrait

Calculabilité - Décidabilité (LI347) Cours n o 5

S. Graillat (Univ. Paris 6)

Stef Graillat Université Pierre et Marie Curie (Paris 6)

LI347 (cours n˚5)

Résumé du cours précédent

.S

1 / 36

Propriété de fermeture des langages réguliers : union, intersection, complémentaire, différence, fermeture, concaténation, renversement Coûts des conversions entre les représentations : AFD, AFN, ε -AFN, ER Propriété de décision des langages réguliers : tester si un langage est vide, si un mot appartient à un langage, si deux langages sont égaux Minimisation d’un automate : un automate reconnaissant le même langage mais avec le moins d’états possibles (unicité de l’automate minimal)

rGiallat(Univ.Paris6)LI347c(uosr˚n)52/36

Partie II : Automates à piles, grammaires hors-contexte et langages hors-contexte

S. Graillat (Univ. Paris 6)

LI347(ou˚5) c rs n

Grammaires et langages hors-contexte

Définition d’un ensemble de langage contenant strictement les langages réguliers. Notation récursive naturelle (les grammaires) Rôle central dans les années 60 pour la compilation Compilation, Parsers, XML Modèle plus puissant, Automates à pile.

S.rGiallatU(inv.aPris6)LI347(coursn˚5)

3 / 36

4/63

Grammaires hors-contexte

Langage défini par les palindromes L pal = { w ∈ Σ ∗ : w = w R } Par exemple otto ∈ L pal , laval ∈ L pal Posons Σ = { 0 , 1 } Application du lemme de pompage : L pal n’est pas régulier ! Soit n donné par le lemme de pompage, regarder 0 n 10 n .

Définition récursive du langage : Base : ε , 0 et 1 sont des palindromes Induction : Si w est un palindrome, 0 w 0 et 1 w 1 le sont aussi Fermeture : seuls les mots obtenus de cette façon sont des palindromes

S. Graillat (Univ. Paris 6) LI347 (cours n˚5)

Grammaires hors-contexte (suite)

Les grammaires hors-contexte sont un « mécanisme formel » pour des definitions telles que celle de L pal P → ε P → 0 P → 1 P → 0 P 0 P → 1 P 1 0 et 1 sont des symboles terminaux P est une variable (non terminale) P est aussi le symbole de départ Les P → α sont des règles de production

.SrGiallat(Univ.Paris)6IL347c(uosr˚n)5

5 / 36

6/36

in.vtaU(iall.SrG(couI347s6)LPari

Définition formelle

63

Une grammaire hors-contexte est un quadruplet G = ( V , T , P , S )

LI347(cou˚5) rs n

S. Graillat (Univ. Paris 6)

Exemples

˚nsr/8)5

7 / 36

Exemple 2 : les expressions régulières sur { 0 , 1 } peuvent être définies par la grammaire G expreg = ( { E } , { 0 , 1 } , A , E ) avec A = { E → 0 , E → 1 , E → E . E , E → E + E , E → E ∗ , E → ( E ) }

où

V est un ensemble fini de variables (ou non terminaux). Chacune d’elle représente un langage. T est un ensemble fini de symboles formant les mots du langage (alphabet). Ce sont les symboles terminaux . P est un ensemble fini de règles de production (ou de réécriture ou de dérivation) de la forme A → α où A est une variable et α ∈ ( V ∪ T ) ∗ S représente le langage à définir par la grammaire ( symbole de départ ou axiome ).

Exemple 1 : G pal = ( { P } , { 0 , 1 } , A , P ) avec A = { P → ε, P → 0 , P → 1 , P → 0 P 0 , P → 1 P 1 } Il arrive que l’on regroupe les règles de production qui commence par la même variable, A = { P → ε | 0 | 1 | 0 P 0 | 1 P 1 }

Exemples (suite) Exemple 3 : La grammaire G est définie à l’aide des variables { E , I } , définit un langage construit sur les symboles { + , ∗ , ( , ) , a , b , 0 , 1 } , la variable E représente le langage à définir ; les règles de production sont 1 . E → I 2 . E → E + E 3 . E → E ∗ E 4 . E → ( E ) 5 . I → a 6 . I → b 7 . I → Ia 8 . I → Ib 9 . I → I 0 10 . I → I 1 Langages avec opérateurs + , ∗ et identifiants dans ( a + b )( a + b + 0 + 1 ) ∗ S. Graillat (Univ. Paris 6) LI347 (cours n˚5) 9 / 36 Dérivations Inférer que certains mots appartiennent au langage d’une variable Inférence récursive : On part des symboles (de l’alphabet) et on va jusqu’au mot. Dérivation : On étend le symbole de départ via une des productions et on le remplace par l’une de ses productions (jusqu’à dériver notre mot) Chaîne Langage Règle Chaîne utilisée 1 . E → I ( i ) a I 5 − 2 . E → E + E ( ii ) b I 6 − 3 . E → E ∗ E 4 . E → ( E ) ( ( i ii v i ) ) b b 0 00 I I 9 9 ( ( i i i ii ) ) 5 . I → a 6 . I → b ( v ) a E 1 ( i ) 7 . I → Ia ( vi ) b 00 E 1 ( iv ) 8 . I → Ib ( vii ) a + b 00 E 2 ( v ) , ( vi ) 9 . I → I 0 ( viii ) (a+b00) E 4 ( vii ) 10 . I → I 1 ( ix ) a ∗ ( a + b 00 ) E 3 ( v ) , ( viii ) S. Graillat (Univ. Paris 6) LI347 (cours n 5) 10 / 36 ˚

lat(Univ.Paris6)IL43(7ocruns5˚1)362/

Soit G = ( V , T , P , S ) une grammaire hors-contexte, A ∈ V une variable, α, β ∈ ( V ∪ T ) ∗ et A → γ ∈ P une règle de production Alors on écrit

α A β ⇒ G αγβ

Dérivations (suite)

Exemple : Dérivation de a ∗ ( a + b 000 ) à partir de E :

11 / 36

Extension : ⇒ ∗ Base : soit α ∈ ( V ∪ T ) ∗ , alors α ⇒ ∗ α Induction : Si α ⇒ ∗ β et β ⇒ γ alors α ⇒ ∗ γ .

E ⇒ E ∗ E ⇒ I ∗ E ⇒ a ∗ E ⇒ a ∗ ( E ) ⇒ a ∗ ( E + E ) ⇒ a ∗ ( I + E ) ⇒ a ∗ ( a + E ) ⇒ a ∗ ( a + I ) ⇒ a ∗ ( a + I 0 ) ⇒ a ∗ ( a + I 00 ) ⇒ a ∗ ( a + b 00 ) Remarque : à chaque étape, il se peut qu’il y ait plusieurs choix pour les règles à appliquer : I ∗ E ⇒ a ∗ E ⇒ a ∗ ( E ) ou I ∗ E ⇒ I ∗ ( E ) ⇒ a ∗ ( E )

LI347 (cours n˚5)

Dérivations (suite)

S. Graillat (Univ. Paris 6)

liarG.S

13 / 36

E ⇒ d E ∗ E ⇒ d E ∗ ( E ) ⇒ d E ∗ ( E + E ) ⇒ d E ∗ ( E + I ) ⇒ d E ∗ ( E + I 0 ) ⇒ d E ∗ ( E + I 00 ) ⇒ d E ∗ ( E + b 00 ) ⇒ d E ∗ ( I + b 00 ) ⇒ d E ∗ ( a + b 00 ) ⇒ d I ∗ ( a + b 00 ) ⇒ d a ∗ ( a + b 00 )

E ⇒ g E ∗ E ⇒ g I ∗ E ⇒ g a ∗ E ⇒ g a ∗ ( E ) ⇒ g a ∗ ( E + E ) ⇒ g a ∗ ( I + E ) ⇒ g a ∗ ( a + E ) ⇒ g a ∗ ( a + I ) ⇒ g a ∗ ( a + I 0 ) ⇒ g a ∗ ( a + I 00 ) ⇒ g a ∗ ( a + b 00 ) Dérivation à droite ⇒ d : on remplace toujours la variable la plus à droite Exemple :

Dérivation à gauche ⇒ g : on remplace toujours la variable la plus à gauche Exemple :

Définition 1 Soit G = ( V , T , P , S ) une grammaire hors-contexte. Le langage de G est défini par L ( G ) = { w ∈ T ? | S ⇒ ? w } On parle alors de langages hors-contexte (ou algébriques ) Autrement dit, L ( G ) est l’ensemble des mots de T ∗ que l’on peut dériver à partir du symbole de départ S

Langage d’ ne grammaire u

S. Graillat (Univ. Paris 6) LI347 (cours n˚5)

)14/36

Dérivations à gauche, dérivations à droite

coursn˚5)6IL43(7viP.rasilial(tnUSG.ar

Langage d’une grammaire (exemple)

Soit G pal = ( { P } , { 0 , 1 } , A , P ) avec A = { P → ε, P → 0 , P → 1 , P → 0 P 0 , P → 1 P 1 } Théorème 1 L ( G pal ) = { w ∈ { 0 , 1 } ∗ : w = w r } = L pal Preuve : “ ⊃ ” Supposons w = w R . Montrons par induction sur la longueur de w que w ∈ L ( G pal ) Base : Si | w | = 0 ou | w | = 1 alors w est ε , 0 ou 1. Puisqu’on a les règles P → ε , P → 0, P → 1, on en déduit que P ⇒ ∗ w . Induction : Soit n ≥ 2 et supposons que tout mot w vérifiant w = w R et | w | ≤ n implique que w ∈ L ( G pal ) . Prenons w tel que w = w R et | w | = n + 1 et montrons que w ∈ L ( G pal ) .

S. Graillat (Univ. Paris 6) LI347 (cours n˚5)

Langage d’une grammaire (exemple)

15 / 36

Comme w = w R , on a w = 0 x 0 ou w = 1 x 1 avec x = x R et | x | ≤ n . Si w = 0 x 0 alors par hypothèse on sait que P ⇒ ∗ x . Mais alors P ⇒ 0 P 0 ⇒ ∗ 0 x 0 = w Par conséquent w ∈ L ( G pal ) . Le cas de w = 1 x 1 est similaire. “ ⊂ ” Supposons que w ∈ L ( G pal ) . Montrons par induction sur la longueur = R de dérivation que w w . Base : Si la dérivation P ⇒ ∗ w est de longueur 1 alors w est égale à ε , 0, ou 1 qui sont des palindromes.

S. Graillat (Univ. Paris 6) LI347 (cours n˚5)

16 / 36

uéiqplapsteeglrèerèimerp ,1rueugn sque i tel i etToncXtsdeelix i XI.àenu isPuelquuengp.ur snoi ol edrédstavi sontdeloesrèglesgsuahcdeseaptrei dnI .iarv S:noitcu héetclonsteeèmor oprurviaseelottunsleupporèmethéo ueugdedrviréoitaucndontirlsuonal sr=w 1 X 2 X∙∙X∙e n dt np. Base:Sip=0alo

S. Graillat (Univ. Paris 6)

Langage d’une grammaire (exemple)

17 / 36

LI347 (cours n˚5)

63

Propriété fondamentales des grammaire hors-contexte

1)/8ns5˚

Induction : Soit n ≥ 1 et supposons que pour tout dérivation P ⇒ ∗ w de longueur n on ait w = w R . Soit alors la dérivation P ⇒ ∗ w de longueur n + 1. On doit donc avoir P ⇒ 0 P 0 ⇒ ∗ 0 x 0 = w P ⇒ 1 P 1 ⇒ ∗ 1 x 1 = w où la deuxième dérivation est faite en n étapes. Alors x est un palindrome ( x = x R ) et par conséquent w qui vaut 0 x 0 ou 1 x 1 est encore un palindrome. 

eutn k Xw⇒raocsnqé,...,n S k pourk=1 nU(tP.viarG.alli7(34urcoisarLI6) ...,ew 1 ,lsquw n te w ∗ X i T e ⇒ i opru⇒ kk w.,..1,k=+1ti1ei− =w n,..., P n w... 1 w X 1 ∙∙∙X i−1 X i X i+1 ∙∙∙ n XX⇒∙ 1 ∙∙ i X 1−i T +1 X i ∙X∙∙ ∗ w n ⇒ rhPatopyesèheli,tsix S.etutiooc-sxetnirmaorehne)uamgrV(T,P,S, 2e osti=G Théorèm poe,stxi i= uttour. ∗ )T∪V(∈elisrolA n ⇒ ∗ w∙∙∙XX i ,wavec iravenéd 1 X 2 X itno One:israneonripa w 1 w=∙∙∙ 2 P . n w vuer ∗ telqueX i ⇒ ∗ w i etw,1..,.,n i w(∈∪V)T

Forme syntaxique

Définition 2 Soit G = ( V , T , P , S ) une grammaire hors-contexte et α ∈ ( V ∪ T ) ∗ . Si S ⇒ ∗ α on dit que α est une forme syntaxique . Si S ⇒ g w , on parle de forme syntaxique gauche et si S ⇒ d w , on parle de forme syntaxique droite Remarque : L ( G ) est donc l’ensemble des formes syntaxiques qui sont dans T ∗

S. Graillat (Univ. Paris 6)

Arbres de dérivation

LI347 (cours n˚5)

Représentation des dérivations par un arbre. Structure de données pour représenter le source d’un programme. Facilite la traduction du source vers un exécutable. Relations entre arbres de dérivations, dérivations et inférences.

S.rGialltaU(in.vaPris)6IL347(cours˚n)5

19 / 36

02/36

.SllatGraiv.Pa(Uni

Construction des arbres de dérivations (exemple)

Définition 3 Soit G = ( V , T , P , S ) une grammaire hors-contexte. Un arbre est un arbre de dérivation pour G si Chaque nœud représente une variable de V Chaque feuille représente soit un symbole terminal soit ε soit une variable. S’il s’agit de ε il doit être le seul et unique fils de son père. Si un nœud interne représente A et ses enfants X 1 , . . . , X k alors A → X 1 ∙ ∙ ∙ X k est une production de la grammaire.

Productions d’un arbre de dérivation tel que : Chaque feuille représente un symbole terminal ou ε La racine est le symbole de départ.

S. Graillat (Univ. Paris 6) LI347 (cours n˚5)

21 / 36

(c47rsous6riI3)L

Dans la grammaire 1 . E → I 2 . E → E + E 3 . E → E ∗ E 4 . E → ( E ) l’exemple suivant est un arbre de dérivations

Construction des arbres de dérivations

6

L’arbre de dérivations montre la dérivation E ⇒ ∗ I + E

I

E + E

E

)5˚n3/22