Grammaires et expressions régulières

lundi 19 juillet 2010
par  Alain BUSSER

Différentes définitions ont été données pour ce qui pourrait être les langages les plus simples, et une fois de plus, on s’est rendu compte, à l’usage, qu’elles coïncident. Les adjectifs régulier, linéaire et rationnel sont donc synonymes dans la théorie des langages.

Grammaires transformationnelles

Dans cet exemple, on ne va pour une fois pas regarder les mots comme concaténation de lettres, mais les phrases comme concaténation de mots (la concaténation étant représentée par le caractère « espace »). On part d’un axiome (ou gabarit de phrase) que voici :


SUJET VERBE COMPLÉMENT.

Pour transformer ce gabarit en phrase, on effectue des transformations comme

  • SUJET -> ARTICLE NOM ADJECTIF
  • SUJET -> ARTICLE NOM ADJECTIF PROPOSITION
  • VERBE -> poursuit
  • COMPLÉMENT -> ARTICLE NOM ADJECTIF
  • COMPLÉMENT -> ARTICLE NOM ADJECTIF PROPOSITION

La règle du milieu est différente des autres en ce qu’elle remplace le mot « VERBE » par un verbe, qui ne pourra plus être transformé par la suite. On dit que le mot « poursuit » appartient au vocabulaire terminal, des mots comme « VERBE » et « PROPOSITION » étant considérés comme non terminaux. Pour l’instant la phrase devient


ARTICLE NOM ADJECTIF PROPOSITION poursuit ARTICLE ADJECTIF PROPOSITION.

Après ça d’autres transformations peuvent être appliquées aux nouveaux mots non terminaux qui sont apparus ci-dessus, comme celles-ci :

  • ARTICLE -> Une
  • ARTICLE -> le
  • NOM -> chat
  • NOM -> souris
  • ADJECTIF -> rose
  • ADJECTIF -> verte
  • PROPOSITION -> PRONOM VERBE COMPLÉMENT
  • PROPOSITION -> PRONOM SUJET VERBE COMPLÉMENT

À ce stade, la phrase en construction devient


Une souris verte qui VERBE COMPLÉMENT poursuit le chat rose que SUJET VERBE COMPLÉMENT.

On voit que les propositions subordonnées font intervenir la récursivité, et d’autres transformations analogues permettent d’arriver successivement à ceci :


Une souris verte qui courait dans ARTICLE NOM poursuit le chat rose que des fous en blouse blanche ont, lui aussi, conçu dans un laboratoire sur lequel VERBE COMPLÉMENT.

puis


Une souris verte qui courait dans l’herbe poursuit le chat rose que des fous en blouse blanche ont, lui aussi, conçu dans un laboratoire sur lequel on a cloué une pancarte portant l’écriture « Ici on fabrique des mammifères transgéniques ».

(Sémantiquement parlant, l’exemple ci-dessus n’est pas de la science-fiction, comme le montre l’exemple que voici)

Retour aux lettres concaténées pour former des mots : Au vocabulaire V=\left\{a,b,c,...\right\} on joint un vocabulaire non terminal U=\left\{X,Y,Z,...\right\} (l’usage est de représenter par des minuscules les lettres terminales et par des majuscules les lettres non terminales). On considère des règles de dérivation du style X\rightarrow abacYaXZ (on transforme une lettre non terminale en mot comprenant éventuellement aussi des lettres non terminales) et un axiome, en général noté X (une lettre non terminale).

Alors l’ensemble des mots terminaux obtenus par ces dérivations est un langage, dit engendré par la grammaire transformationnelle.

L’utilisation de mots tels que dérivation et axiome suggère que l’activité consistant à démontrer des théorèmes, revient à engendrer un langage (l’ensemble des théorèmes). C’est effectivement le cas : Démontrer c’est réécrire (sauf que là il y a plusieurs axiomes).

Équivalence

On appelle linéaire un langage pour lequel les règles de transformation sont toutes de la forme

  • X -> aY
  • X -> a

a est une lettre terminale, et X et Y des lettres non terminales. Un langage linéaire est donc un langage qui se construit de gauche à droite (sans tenir compte du contexte). L’adjectif linéaire est aussi lié au fait que les langages linéaires sont de la forme \varphi^{-1}(M)M est un monoïde, et \varphi un morphisme de monoïdes (donc quelque chose de linéaire).


Un automate fini est un graphe dont les nœuds sont les états du graphe, et les arêtes représentent les changements d’état de l’automate. Chaque changement d’état a lieu lors de la lecture d’une lettre. Un automate fini n’a qu’un seul état initial, et un ou plusieurs états finaux.

On dit que l’automate lit un mot si, mis dans son état initial, l’automate lit, une à une, de gauche à droite, les lettres du mot, en suivant les arêtes du graphe pour changer d’état.

On dit qu’un mot est reconnu ou accepté par l’automate si, après avoir lu le mot, l’automate est dans un de ses états finaux (ou accepteurs).

Un langage est dit régulier s’il existe un automate fini reconnaissant les mots de ce langage et uniquement ceux-là.

Des exemples sont visibles (avec leurs automates) dans les onglets suivants. Les automates y sont simulés avec le logiciel DFA Simulator.


Un langage rationnel est un langage engendré à partir de langages finis par un nombre fini de répétitions des constructions suivantes :

  • A.B qui est l’ensemble des concaténés des éléments de A et de ceux de B ;
  • A|B qui est la réunion A \cup B de A et de B (Kleene note la réunion par le trait vertical de la disjonction logique, ce qui est logique) ;
  • A^* qui est l’ensemble des mots obtenus par concaténation d’un choix quelconque d’éléments de A.

Les langages rationnels (pour savoir pourquoi on les appelle comme ça, voir l’onglet « fractions ») peuvent aussi être décrits par les propriétés qu’un mot doit vérifier pour appartenir à un tel langage ; ces propriétés sont décrites par des expressions rationnelles ou expressions régulières, en abrégé RegExp. De bons logiciels pour manipuler les RegExp sont Kodos et Kiki, écrits en Python (langage).


En effet les définitions des langages linéaire, régulier, rationnel ou reconnu par un monoïde (de la forme \varphi^{-1}(M)) sont équivalentes, et désignent donc le même genre de langages.

Dans les autres onglets, on va voir des exemples, définis de différentes manières (grammaire transformationnelle, automate fini, RegExp), à fin de comparaison entre les différentes manières de décrire ces langages.

Suites convergentes

Dans l’article précédent, on a vu que le langage décrit par les itérés de la suite logistique, avec k<2, est l’ensemble des mots qui commencent par un certain nombre de « g » de suite, suivis par un certain nombre de « d ». Ici on utilise des lettres minuscules pour « gauche » et « droite » parce qu’elles sont terminales. La RegExp correspondante (en remplaçant les mots infinis de l’article précédent par des versions finies) est

g*d+

(un certain nombre de « g » suivi par au moins un « d »). Elle décrit l’ensemble des mots de la forme g^a d^ba \in \N et b\geqslant 1.


Une grammaire transformationnelle pour ce langage est formée de l’axiome X et des règles

  1. X\rightarrow Xd
  2. X \rightarrow d
  3. X \rightarrow Y
  4. Y \rightarrow Yg
  5. Y \rightarrow g

Voici par exemple la dérivation du mot gggddddd :

  • X (axiome)
  • Xd (règle 1)
  • Xdd (règle 1 à nouveau)
  • Xddd (encore la règle 1)
  • Xddddd (règle 1)
  • Yddddd (règle 3)
  • Ygddddd (règle 4)
  • Yggddddd (règle 4)
  • gggddddd (règle 5)

La dérivation est terminée par qu’il ne reste plus de lettre non terminale à laquelle on puisse appliquer une règle.


L’automate reconnaissant ce langage est présenté ci-dessous, tout d’abord en reconnaissant le mot « GGGDDDDD » :

puis en refusant le mot « GGDDDDGDG » :

Sarkovski

On a vu dans l’article précédent que pour d’autres valeurs du paramètre k, le mot est formé d’une succesion périodique de « gdd » et correspond (si on veut le rendre fini) au langage décrit par la RegExp

(gdd)*

Une grammaire générative est formée de l’axiome X et des deux règles

  1. X\rightarrow Xgdd
  2. X \rightarrow gdd

L’automate reconnaissant ce langage est vu ci-dessous en train de reconnaître le mot « GDDGDD » (on constate que l’état q0 est à la fois initial et final) :

Décimaux

Les nombres décimaux, écrits en écriture décimale, forment un langage régulier. Voici comment il peut être décrit par une RegExp :

[0-9]*(.[0-9]+)?
  • « [0-9]* » : un certain nombre de caractères compris entre 0 et 9,
  • suivi par zéro ou une occurence («  ? ») des parenthèses : point décimal, suivi dans ce cas nécessairement par au moins un (« + ») chiffre décimal.

Dans ce cas particulier, l’importance des chiffres comme caractères justifie qu’on utilise l’abréviation « \d » à la place de « [0-9] » :

\d*(.\d+)?

Voici une grammaire transformationnelle pour engendrer les « mots » de ce langage (les nombres décimaux positifs) : L’unique axiome est toujours X, et certaines des règles de dérivation sont ci-dessous :

  • X \rightarrow 1X
  • X \rightarrow 2X
  • X \rightarrow 3X
  • X \rightarrow 4X
  • X \rightarrow 5X
  • X \rightarrow 6X
  • X \rightarrow 7X
  • X \rightarrow 8X
  • X \rightarrow 9X
  • X \rightarrow .Y
  • Y \rightarrow 0Y
  • Y \rightarrow 1Y
  • Y \rightarrow 2Y
  • Y \rightarrow 3Y
  • Y \rightarrow 4Y
  • Y \rightarrow 5Y
  • Y \rightarrow 6Y
  • Y \rightarrow 7Y
  • Y \rightarrow 8Y
  • Y \rightarrow 9Y

et les règles de terminaison comme Y \rightarrow 3.


Un automate fini reconnaissant ce langage est montré ci-dessous, d’abord en reconnaissant un nombre entier (sans partie décimale) :

ensuite en reconnaissant un nombre vraiment décimal :

enfin en refusant un code qui n’est pas un nombre (il y a deux points qui ne peuvent donc pas être des points décimaux) :


Cependant, outre le fait que certains nombres décimaux sont négatifs, on ne commence ni ne finit jamais d’écriture décimale par un 0. Voici une RegExp qui convient mieux :

^(\+|-)?[1-9][0-9]*(\.[0-9]*[1-9])?

(d’autres exemples intéressants notamment dans le domaine monétaire peuvent être trouvés ici)

Voici un automate fini reconnaissant les nombres décimaux relatifs, sans chiffre 0 ni au début ni à la fin :

L’état initial « signe » s’occupe du signe éventuel, q1 s’occupe du premier chiffre (non nul), q2 des autres signes, q3 (état final) des chiffres décimaux, et q4 représente les limbes où vont tous les caractères non corrects.

Fractions

La suite des décimales d’une fraction est aussi un langage régulier, c’est d’ailleurs pour cela qu’on appelle « rationnel » un langage régulier. Par exemple, la suite des décimales de \frac{1}{7} est périodique de période 142857.

La RegExp correspondante décrit un certain nombre de répétitions de 142857 noté (142857)*, suivi éventuellement par une période incomplète, notée par la liste des possibilités, séparées par des disjonctions :

(142857)*(|1|14|142|1428|14285)

Et en notant respectivement A, B, C, D, E et F les lettres non terminales destinées à être remplacées respectivement par les lettres terminales 1, 4, 2, 8, 5 et 7, la grammaire transformationnelle suivante la décrit :

  • F \rightarrow F1
  • A \rightarrow A4
  • B \rightarrow B2
  • C \rightarrow C8
  • D \rightarrow D5
  • E \rightarrow E7
  • A \rightarrow 1
  • B \rightarrow 4
  • C \rightarrow 2
  • D \rightarrow 8
  • E \rightarrow 5
  • F \rightarrow 7

Le fait que le développement décimal est périodique se voit dans l’aspect circulaire de l’automate (comme d’ahabitude, un état non terminal q6 sert à reléguer dans les limbes de l’infâmie, tout caractère extérieur au langage). Voici comment l’automate reconnaît le mot « 14285714 » qui forme les 8 premières décimales de \frac{1}{7} :

Voici maintenant deux expressions non reconnues par l’automate, 142856 n’est pas reconnue parce que 6 n’est même pas dans le vocabulaire de ce langage, et 142858 n’est pas reconnue parce que le 5 doit être suivi par un 7 et pas par un 8 :

Musique

Le style d’un compositeur peut largement s’expliquer par des suites d’accords qu’il aime bien utiliser, et il peut arriver que le langage décrivant ces suites d’accords soit régulier. Voir par exemple les travaux de Marc Chemillier au sein de l’IRCAM, en particulier dans le cas du jazz, qui a inspiré l’exemple suivant, qui est la très célèbre grille de blues en 12 mesures :

On note 1 l’accord de tonique, par lequel on commence et parfois finit la strophe de blues, par exemple en do, c’est l’accord de do septième noté C7 (ou plus généralement I7). De même 4 représente l’accord de sous-dominante IV7 (par exemple en do c’est fa septième), qui sert d’accord de passage, et 5 l’accord de dominante V7 (en do c’est sol septième). Alors comme le 4 n’est jamais suivi par le 5, et qu’on ne s’attarde pas trop sur le 5, la RegExp suivante décrit une suite d’accords qui sonne « blues » :

(1|(4+1)|5(|4+1))*5?

Il lui correspond la grammaire transformationnelle suivante :

  • A \rightarrow 1A
  • A \rightarrow 4B
  • A \rightarrow 5C
  • B \rightarrow 1A
  • B \rightarrow 4B
  • C \rightarrow 1A
  • C \rightarrow 4B
  • A \rightarrow 1
  • A \rightarrow 5
  • B \rightarrow 1
  • C \rightarrow 1

Avec ce langage, la grille classique d’un blues en 12 mesures :

I7 IV7 I7 I7
IV7 IV7 I7 I7
V7 IV7 I7 V7

s’écrit 141144115415, qui est reconnu par l’automate :

La grille d’un blues en 8 mesures est également reconnue :

I7 I7 IV7 I7
V7 I7 IV7 I7

(chaîne 11415141)

mais même la grille classique en 12 mesures a subi des enrichissements du langage qui nécessitent des automates beaucoup plus complexes ; le record est détenu par Blues for Alice, de Charlie Parker.

Dans le prochain article, on étudiera des « grammaires indépendantes du contexte », qui ne sont pas régulières, mais l’objet RegExp de JavaScript aidera à les gérer dans un contexte à la fois graphique et botanique.


Commentaires

Navigation

Articles de la rubrique

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 11 octobre 2017, 14h-18h, campus du Tampon
- Mercredi 22 novembre 2017, 14h-18h, campus du Tampon
- Mercredi 7 février 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 7 mars 2018, 14h-18h, campus du Tampon
- Mercredi 4 avril 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 2 mai, 14h-18h, campus du Tampon
- Mardi 5 juin 2018, PTU, Saint-Denis, salle S23.6
- Mercredi 6 juin, 14h-18h, campus du Tampon

Fête de la science

Du 13 au 18 novembre 2017.
Thème : « La recherche à l’heure du numérique »

Semaine des mathématiques

Du 26 au 31 mars 2018.
Thème : « Mathématiques et mouvement »


Brèves

Décès de Roger Mohr

mardi 27 juin

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

dimanche 22 octobre 2017

Publication

772 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

714 aujourd'hui
782 hier
2133183 depuis le début
29 visiteurs actuellement connectés