Nous présentons maintenant une méthode pratique pour déclarer des langages rationnels souvent de façon plus simple et donc plus lisible que sous forme d'expressions compliquées.
Pour des raisons de commodité de notation, il est pratique donner des noms aux expressions rationnelles et de définir ensuite de nouvelles expressions rationnelles en utilisant ces noms comme s'ils étaient des symboles. La seule précaution à prendre est d'éviter les confusions en choisissant judicieusement les noms que l'on associe aux expressions rationnelles. Dans la définition qui suit, qui introduit la notion de définition rationnelle, nous utilisons pour cela les caractères gras.
Exemple : les identificateurs en Pascal sont définis par :
NB : Lex est un outil permettant de générer des programmes de reconnaissance de mots (analyseurs lexicaux) à partir d'une suite de définitions rationnelles (Lex est présenté plus loin).
On remarque que chaque membre gauche (ri) d'une règle (di → ri) ne peut faire intervenir que les nouveaux symboles définis antérieurement (les dj tels que j<i) et donc on n'a pas, dans le cas général, de définition récursive, comme le serait par exemple la définition caractérisée par l'unique règle X → aXb|ab, qui engendre pour X le langage {anbn | n ∈ N}. En effet, si l'on autorisait l'écriture de définitions récursives, on pourrait caractériser des langages qui ne sont pas rationnels, comme par exemple {anbn | n ∈ N}, ci-dessus. Ces définitions récursives seront d'ailleurs utilisées pour construire d'autres classes de langages, à l'aide de "grammaires", comme nous le verrons dans un prochain chapitre.
Par contre, il est possible d'autoriser une forme de récursivité : la récursivité droite, c'est-à-dire des définitions de la forme X → xX|y avec x et y des expressions rationnelles. Par exemple, la définition suivant est autorisée : X → aX|a. Elle engendre pour X le langage {an | n ∈N}. Donc X → aX|a est équivalente à X → a+.
Exercices et tests :
Exercice 4.1. Donner l'alphabet et les définitions rationnelles permettant de décrire le langage dont les mots sont les nombres décimaux.
Exercice 4.2. Expression des cellules sous Excel
Sous Excel, une cellule est repérée par son numéro de ligne et son numéro de colonne (exprimé en lettres). Par exemple, « L2 » définit la cellule en ligne « 2 » et colonne « L ». De même, « AB23 » définit la cellule en ligne « 23 » et colonne « AB ».
Une zone est indiquée par la cellule en haut à gauche et la cellule en bas à droite, toutes les deux séparées par deux points (« : »). Par exemple, « L2:M6 » indique la zone allant de la cellule « L2 » à la cellule « M6 ». L’ordre des cellules n’importe pas. Par exemple, « M6:L2 » est identique à « L2:M6 ».
Une colonne entière est définie par son nom seul. Par exemple, « L:L » indique la zone contenant toute la colonne « L ». De même, une ligne est définie par son numéro seul.
Une zone peut être aussi une seule cellule ou une suite de zones séparées par « ; ». Par exemple, « M6 ; A3:C18 ; G:I ; 4:18 » indique la zone composée de la cellule « M6 », de la zone « A3:C18 », des colonnes « G » à « I » et des lignes 4 à 18.
Écrire l’expression rationnelle décrivant une zone sous Excel. Vous utiliserez la notation des définitions rationnelles pour simplifier l’expression.
Exercice 4.3. Expression de polynômes
On cherche à écrire le langage des polynômes de la variable x à coefficients entiers. Les polynômes ne sont pas nécessairement réduits (il peut y avoir plusieurs monômes de même degré), ni ordonnés. Le polynôme nul existe et se note 0. Les monômes, quant à eux, doivent être réduits selon les conventions habituelles. Quand ils ne peuvent pas être réduits, ils sont composés d'un coefficient à un chiffre suivi de x et de l'exposant à un chiffre. Le produit entre le coefficient et la variable est une simple concaténation, l'opérateur d'élévation à la puissance est "^".
En utilisant les définitions rationnelles, donner une expression rationnelle, la plus simple possible, qui dénote le langage des polynômes tel qu'il est décrit ci-dessus. Précisez l'alphabet.
mardi, 25/11/03 10:08
