Planche 1

Inf 431 -- Cours 15
Grammaires formelles
http://jeanjacqueslevy.net
secrétariat de l'enseignement:
Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX,
01 69 33 34 67
http://www.enseignement.polytechnique.fr/informatique/IF

Planche 2

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
Bibliographie

John E. Hopcroft , Rajeev Motwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (2nd Edition), Addison-Wesley, 2000.

Dexter C. Kozen, Automata and Computability, Springer, 1999.


Planche 3

Langage régulier (rationnel)



Planche 4

Langage algébrique (context-free)

Planche 5

Langage context-sensitive

Exercice 1 Donner une grammaire pour les langages suivants:
· { anbncndn| n > 0 } · { an2 | n ³ 0 }
· { uu | u Î S* } · { anbncp | n ³ 0, p ³ 0 } È { anbpcp | n ³ 0, p ³ 0 }

Planche 6

Langages et Grammaires

Un langage L est un ensemble de mots sur l'alphabet S (L Ì S*).

Une grammaire est un 4-uplet G = (S, V
N, S, P)
Planche 7

Classification de Chomsky


type productions catégorie
0 a ® b a ® e  
1 a ® b |a| £ |b| context sensitive
2 A ® b   context-free
3 A ® aB A ® a régulier
a Î V+-S*, b Î V+ et A,B Î VN, a Î S.

Une exception est possible pour l'axiome S:
Planche 8

Langage généré par une grammaire

Planche 9

Notations abrégées

Planche 10

Langage régulier et automate fini

Théorème 1Un langage est régulier si et seulement s'il est généré par un automate fini.
Planche 11

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

Planche 12

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


Planche 13

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

Théorème 2[Kleene] Un langage est régulier si et seulement s'il est décrit par une expression régulière.
Planche 14

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

Pour (a+b)*ab, l'automate est:

En supprimant les e-transitions et en déterminisant, on obtient:

Planche 15

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

Planche 16

Mot vide dans une grammaire algébrique

Exercice 2 Supprimer les parties droites vides dans ces deux grammaires vues au cours 6
S ® e S ® S S S ® a S b
A ® e A ®  [ A   nb   A ]

Planche 17

Forme normale de Chomsky

Toute grammaire algébrique a une grammaire équivalente dont les règles sont de la forme A ® a, A ® BC (a Î S), à l'exception de l'axiome qui peut avoir une règle S ® e.

Démonstration:
Exercice 3 Mettre en forme normale de Chomsky les grammaires de l'exercice précédent.

La forme normale de Chomsky a une application: l'algorithme CYK pour analyser toute grammaire context-free en temps O(n
3)

Planche 18

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

Planche 19

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

Planche 20

Non expressivité

Planche 21

Langage récursivement énumérable

Théorème 3Un langage est de type 0 (dans la classification de Chomsky) ss'il est récursivement énumérable.
Planche 22

Quelques exercices

Exercice 7 Montrer qu'il existe un algorithme pour reconnaître un langage contexte-sensitif, c'est-à-dire répondant oui si le mot d'entrée est dans le langage, et non s'il n'appartient pas.

Exercice 8 Montrer qu'il n'existe qu'un semi-algorithme pour reconnaître un langage récursivement énumérable, c'est-à-dire répondant oui si et seulement si le mot d'entrée est dans le langage. Le programme peut ne pas fournir de réponse si le mot n'est pas dans le langage.

Exercice 9 Montrer qu'il existe une analyse descendante fonctionnant pour tout langage algébrique, mais avec retours en arrière (backtracking) dans le mot d'entrée. Complexité?

Exercice 10 Quel est la notion d'arbre syntaxique pour les langages non algébriques?

Exercice 11 Donner un algorithme pour trouver les non-terminales A telles que A ¾®
* e dans un langage algébrique.

Exercice 12 Donner un algorithme pour trouver les non-terminales A telles que A ¾®
* B (B Î VN) dans un langage algébrique.


This document was translated from LATEX by HEVEA.