Grammaires et algèbre

jeudi 15 juillet 2010
par  Alain BUSSER

Il y a

  • Les papous papas à poux papas ;
  • Les papous papas à poux pas papas ;
  • Les papous pas papas à poux papas ;
  • Les papous pas papas à poux pas papas ;
  • Les papoux papas pas à poux ;
  • Les papous pas papas pas à poux ;

et c’est tout !

Soit un ensemble V=\left\{a, b, c ... \right\} appelé vocabulaire. Les éléments de V sont appelés mots ou caractères. On appelle langage, ou grammaire, un ensemble de chaînes de caractères construites à partir des éléments de V.

On note V^* l’ensemble de toutes les chaînes de caractères construites à partir des éléments de V. On peut donc dire qu’une grammaire est un sous-ensemble de V^*. On dit parfois mot (voir plus bas) pour un élément de V^*. En effet, le mot « mot » est plus simple que l’expression « chaîne de caractères »...

Comme \emptyset \subset V^*, le plus simple des mots est le mot vide qui s’écrit avec aucun caractère (parfois des caractères spéciaux ou invisibles).

Exemple : Le plus simple des vocabulaires non vides est un singleton comme V=\left\{1\right\}. Dans ce cas un mot est une suite de « 1 » collés l’un derrière l’autre (notation utilisée par une machine de Turing pour représenter les entiers naturels en base 1), et un langage un ensemble de tels objets (par exemple la suite de Fibonacci représentable par machine de Turing sous la forme \left\{1, 11, 111, 11111, 11111111, 1111111111111, ... \right\}).

En assimilant les lettres (caractères) d’un mot aux maillons d’une chaîne (la chaîne de caractères : Le mot), l’opération consistant à ouvrir le dernier maillon d’une chaîne A et d’y insérer le premier maillon d’une chaîne B avant de le refermer puis de le ressouder, et qui aboutit à une chaîne plus longue, équivaut ici à l’opération linguistique d’agglutination de mots.

Avant

Après

Pour cette raison, l’opération qui, à deux mots, associe celui qu’on obtient en collant le second après le premier, est appelée concaténation (du latin catena, chaîne). Deux exemples dans la langue malgache (qui est agglutinante et se base donc sur la concaténation pour fabriquer ses mots) :

  1. à partir de Vola (monnaie) et mena (rouge) on obtient par concaténation Volamena (l’or) ;
  2. à partir de Zaza (enfant) et kely (petit) on obtient par concaténation Zazakely (gamin).

Dans Scratch 1.4, la concaténation est appelée « jonction » :

La concaténation vue comme opération algébrique, vérifie 2 des 3 axiomes d’un groupe :

  • Le mot vide est élément neutre (on ne change pas un mot en lui concaténant du rien) ;
  • Elle est associative (par exemple à partir de Volamena (l’or, mot qui est lui-même obtenu par concaténation) et kely (petit) la langue malgache a formé le mot Volamenakely qui bizarrement ne désigne pas une pépite d’or mais une variété de riz...)

Une structure algébrique ayant ces propriétés s’appelle un monoïde.

Langues

La concaténation intervient à plusieurs niveaux dans les langues naturelles :

  1. En concaténant des lettres on obtient des mots. D’où le nom d’alphabet donné à V. Dans ce cas la concaténation est représentée par une absence de caractère.
  2. En concaténant des mots on obtient des phrases. D’où le nom de vocabulaire donné à V. Dans ce cas la concaténation est représentée par le caractère d’espace.
  3. En concaténant des phrases on obtient des paragraphes. Dans ce cas la concaténation est représentée par des signes de ponctuation comme le point.
  4. En concaténant des paragraphes on obtient des textes, et la concaténation est représentée par des retours à la ligne...

À partir de l’alphabet latin, on peut former par concaténation des 26 lettres beaucoup plus de mots que ceux de la langue latine, par exemple « bacrthf » et « zsxckfr » sont des mots qui ne semblent exister dans aucune langue connue. Un langage est donc un sous-ensemble de V qui peut être décrit

  • par une description (liste des propriétés d’un mot qui font qu’il est accepté dans le langage)
  • par un procédé de construction du langage ; on parle alors de grammaire générative et transformationnelle.
  • par un algorithme permettant de savoir, un mot étant donné, s’il appartient ou non au langage. La classification de Chomsky est basée sur la complexité de ces algorithmes.

Le passage du français à l’argot « javanais » peut être considéré comme une règle de réécriture d’une grammaire transformationnelle. Ainsi « javanais » devient « javavavanaivais » dans cet argot imité par Bobby Lapointe dans « Aragon et Castille »...

Le fait que la concaténation n’est pas commutative permet l’existence d’anagrammes et de palindromes.

Suites

Des mots infinis peuvent apparaître dans l’étude de suites itérées comme u_{n+1}=k u_n (1-u_n), en utilisant le codage suivant :

  • Chaque fois que u_k<\frac{1}{2}, la k-ième lettre du mot sera « G » (initiale du mot « gauche » ;
  • Chaque fois que u_k>\frac{1}{2}, la k-ième lettre du mot sera « D » (initiale de « droite ».

On peut convenir que lorsqu’il n’y a que des « G » à partir d’un certain rang, on n’en écrit qu’un, et le mot est alors fini comme dans les autres onglets.

Le mot associé à une suite u_n dépend de son terme initial u_0 mais pour k<2, le langage ne contient qu’un seul mot et celui-ci ne dépend pas de u_0 (on peut modifier u_0 en bougeant à la souris le point bleu sur l’axe des abscisses) :

CarMetal - 13.2 ko
les langages de la fonction logistique

En modifiant k dans la figure ci-dessus, on constate que chaque fois que quelque chose d’intéressant se passe (une « bifurcation ») du point de vue topologique, un changement du langage se produit également (avec k=2 par exemple). L’étude de ces langages infinis s’appelle la dynamique symbolique et elle est foisonnante. Par exemple pour k=4 :

  • L’ensemble des valeurs de u_0 dont le mot commence par GGD par exemple, est l’ensemble des u_0 tels que

u_1<\frac{1}{2}

u_2<\frac{1}{2}

u_3>\frac{1}{2}

C’est un intervalle, il est inclus dans l’ensemble des u_0 dont le mot commence par GG.

  • Ces intervalles sont emboîtés, et leur intersection est le singleton \left\{u_0\right\} : À chaque mot infini écrit dans le vocabulaire V=\left\{ G, D \right\} correspond un unique u_0 \in \left[ 0; 1 \right] : On a une bijection entre \left[ 0; 1 \right] et V.
  • On peut munir V d’une ultradistance telle que cette bijection soit continue : C’est un homéomorphisme (noté \varphi ci-dessous).
  • Ce diagramme commute :

\begin{array}{rrcll}&& 4x(1-x) &&\\ &[0;1] & \hookrightarrow &[0;1] & \\  \varphi & \downarrow && \downarrow \varphi \\ & V^* & \hookrightarrow & V^*& \\ && s &&\end{array}

c’est-à-dire que 4x(1-x)=\varphi^{-1}\left( s\left( \varphi(x) \right) \right) : Les fonctions s et x \mapsto kx(1-x) sont conjuguées. Ce qui veut dire encore que tout ce qui se passe du point de vue de V^* avec s correspond à ce qui se passe du point de vue de [0;1] avec x\mapsto 4x(1-x).

  • Or la fonction s qui est conjuguée à x\mapsto 4x(1-x) est extrêmement simple à « calculer » : C’est celle qui consiste à enlever la première lettre du mot (par exemple s(GGDGDGDDG...)=GDGDGDDG...).

La dynamique symbolique permet alors presque immédiatement de démontrer certaines propriétés de la suite u_n en utilisant la fonction s (première lettre du mot anglais « shift », parce qu’en enlevant la première lettre d’un mot infini, on décale les autres lettres vers la gauche). Par exemple l’existence de points périodiques pour toutes les périodes, le dénombrement des périodes, l’aspect chaotique de la suite logistique u_n ...

Dans le même ordre d’idées, c’est en regardant le mot GGDGGDGGDGGD...=(GGD)^* qu’on démontre l’existence pour k>3,83, d’une « 3-période » c’est-à-dire de trois réels a, b et c tels que 4a(1-a)=b, 4b(1-b)=c et 4c(1-c)=a. C’est aussi avec la dynamique symbolique qu’on démontre le théorème de Sarkovskii.

Codes

La numération décimale est basée sur un vocabulaire V=\left\{0,1,2,3,4,5,6,7,8,9\right\}, et le langage formé par les « mots » écrits à l’aide de ces 10 chiffres, en admettant une règle (ne pas commencer par un 0), est celui des entiers naturels.

Le langage des nombres décimaux s’obtient en ajoutant la lettre « virgule » au vocabulaire, et en ajoutant trois règles d’écriture :

  1. ne placer au maximum qu’une fois la virgule ;
  2. ne pas finir par un 0 ;
  3. commencer par un 0 si c’est le seul chiffre avant la virgule.

On peut étudier des variantes, en ajoutant des espaces entre les groupes de trois chiffres, avec d’autres bases de numération que 10, avec les symboles + et - pour traiter les nombres négatifs, ou avec les « chiffres » V=\left\{I,V,X,L,C,M\right\} des nombres romains...

Avec des chiffres on peut définir d’autres langages que ceux des numérations : Par exemple,

  • une adresse IP s’écrit avec 4 groupes de 3 chiffres séparés par des points,
  • un numéro de téléphone (en France) s’écrit avec dix chiffres ;
  • Un numéro de sécurité sociale en France lui non plus ne peut pas s’écrire avec n’importe quelle suite de 15 chiffres (le premier chiffre ne peut pas être 3, les chiffres 2 et 3 ne peuvent donner 13 car il n’y a que 12 mois dans l’année, etc et les deux derniers chiffres sont calculés à l’aide des précédents avec l’algorithme de la clé RIB)
  • Le nom de cette clé vient de ce qu’elle est utilisée pour les relevés d’identité bancaire, dont les numéros forment eux aussi un langage.

Enfin, un exemple un peu pointu : Il y a 2^{24}=16777216 mots de 3 octets ; ils forment un espace de dimension 24 sur le corps F_2 à 2 éléments. Dans cet espace, le réseau de Leech permet de placer 4096 hypersphères tangentes entre elles, dont les centres sont 2^{12}=4096 points de distance de Hamming maximale. Le langage formé par les coordonnées de ces 4096 points est appelé code de Golay et sert à encoder des mots de 12 bits par des mots de 24 bits, de manière que le changement (par erreurs de transmission) de trois bits soit corrigeable, tout simplement parce que ces trois erreurs déplacent le point à l’intérieur de l’hyperboule centrée sur son ancienne position, et qu’il suffit de le remettre au centre de l’hyperboule pour corriger les trois erreurs. Le code de Golay est très performant parce que 3 bits par paquet de 3 octets, c’est 12,5% d’erreurs sur le canal de transmission que le récepteur n’apercevra même pas.

Algèbre

L’ensemble des expressions algébriques est aussi un langage.

Par exemple, une règle de ce langage est que le nombre de parenthèses ouvrantes doit être égal au nombre de parenthèses fermantes.

Puisqu’une expression est un mot d’un langage, on peut utiliser un arbre syntaxique (utile pour l’algorithmique des compilateurs) pour la représenter. Par exemple l’expression (2x+1)(x-2) s’analyse successivement comme ceci :

  • Un produit ;
    • Le premier facteur est une somme ;
      • Le premier terme du premier facteur est un produit, de 2 par x ;
      • Le deuxième terme du premier facteur est 1 ;
    • Le second facteur est une différence ;
      • Son premier terme est x ;
      • Son deuxième terme est 2.

Cette description, inspirée par les grammaires transformationnelles, est en fait la représentation d’un arbre, que voici :

C’est en lisant l’arbre de gauche à droite qu’on retrouve (2x+1)(x-2) (les parenthèses représentent les sous-arbres). Mais on peut aussi lire l’arbre de haut en bas, ce qui donne la notation polonaise pour l’expression algébrique : *+*2x1-x2 qui ne nécessite pas de parenthèses (elle n’est pas ambigüe).


Lorsqu’on ajoute l’existence pour tout mot non vide, d’un inverse pour la concaténation, on transforme le monoïde en un groupe, et tout groupe peut être décrit comme un langage de ce genre ; on parle alors de présentation par générateurs (les éléments de V) et relations (les axiomes du langage).

Par exemple, le complémentaire du noeud de huit (qui est un espace hyperbolique de dimension 3)

a pour groupe fondamental celui engendré par les trois matrices

a=\frac{1}{2}\left(\begin{array}{rr}3+i\sqrt{3}& -1-i\sqrt{3}\\1+i\sqrt{3}&1-i\sqrt{3} \end{array}\right)

b=\frac{1}{2}\left(\begin{array}{rr}1-i\sqrt{3}& 1+i\sqrt{3}\\-2&2 \end{array}\right)

c=\frac{1}{2}\left(\begin{array}{rr}1& 1+i\sqrt{3}\\0&2 \end{array}\right)

qui vérifient les relations ab^{-1}cb=\left(\begin{array}{rr}1&0\\0&1\end{array}\right) et abc^{-1}a^{-1}c=\left(\begin{array}{rr}1&0\\0&1\end{array}\right). Ces deux relations décrivent le groupe de façon univoque, et elles peuvent s’interpréter comme des règles de réécriture :

b^{-1}cb\rightarrow a

c^{-1}ac\rightarrow ab

Génétique

Le patrimoine génétique des êtres vivants s’écrit dans un langage basé sur un alphabet de 4 lettres V=\left\{A, C, G, T \right\} (pour adénosine, cytosine, guanine et thymine), dans des chaînes de caractères moléculaires : le célèbre ADN.

La concaténation est alors assurée par une nanomachine appelée ADN ligase. L’opération inverse, l’extraction de sous-chaînes de caractères, est réalisée par une autre nanomachine en forme de paire de ciseaux appelée enzyme de restriction. Par exemple, l’enzyme « Eco RI » de la bactérie Escherichia Coli repère la chaîne « GAATTC » et, si elle la trouve, sépare le « G » du « A ». La simulation en RegExp pourrait ressembler à ceci :

ADN.search(/GAATTC/g)

pour ce qui est de la partie recherche de la chaîne virale à combattre (ADN étant une chaîne de caractères).

Des grammaires transformationnelles sont à l’œuvre en génétique. Tout d’abord, la transformation

A \rightarrow T

C \rightarrow G

G \rightarrow C

T \rightarrow A

permet à partir d’une demi-molécule d’ADN, d’obtenir l’autre moitié. Mais aussi

T \rightarrow U

(remplacement de la thymine par de l’uracile) permet, à partir de l’ADN, de fabriquer une molécule d’ARN messager. En effet, si on compare un être vivant à un ordinateur, l’ADN est un peu l’équivalent du disque dur, et l’ARN est la RAM où figure une copie d’un extrait du disque dur. Le rôle du CPU est alors assuré par des ribosomes, qui ressemblent à des machines de Turing, à ceci près que si une machine de Turing lit et écrit sur une même bande, le ribosome lit de l’ADN et écrit (ou crée) sur une autre molécule, une protéine. Une autre différence entre un ribosome et une machine de Turing est que la même bande (l’ARN) peut être lue simultanément par plusieurs robosomes : La vie est un calcul parallèle... Les ribosomes lisent en fait un langage basé sur des mots de trois lettres, appelé code génétique.

Un exemple (un peu simplifié) :

Le morceau d’ADN que voici

...ATGGTAGTCGTGGTTTAG...

devient après transcription, l’ARN suivant :

...AUGGUAGUCGUGGUUUAG...

Le mot formé par les trois premières lettres, « AUG », est équivalent au « begin » du langage Pascal : Il signifie que c’est ici que le ribosome doit commencer son travail. De même, « UAG » est un codon « stop » qui provoque l’arrêt de la machine de Turing, pardon, du ribosome. Ensuite, « GUA » provoque l’assemblage d’une molécule de valine, puis « GUC », « GUG », « GUU » en font de même (il y a ambiguïté du langage), et, une fois que ces 4 molécules de valine sont assemblées, le codon « UAG » provoque la fin de le fabrication de cette nanoprotéine. La puissance de « calcul » de l’ADN vient de ce que, parmi les protéines ainsi synthétisées, il y en a qui deviennent des parties de ribosomes, d’autres qui deviennent des adn ligases ou enzymes de restriction : Indirectement, un ADN peut « fabriquer » un autre ADN.

Ci-dessous, un ADN est synthétisé (il n’obéit pas forcément au code génétique), puis transcrit en ARN (seul le début est affiché, en bleu pour l’ADN, en vert pour l’ARN), et le nombre de codons stop « TAG » qui ont été tagués dans cet ADN, est cherché puis affiché en rouge. Pour voir l’effet de cette simulation, cliquer sur le script en haut à gauche (on peut le faire plusieurs fois mais dans ce cas il est recommandé d’annuler les effets avant) :

CarMetal - 1.2 ko
la simulation d’ADN

Le nombre d’apparitions du marqueur génétique TAG dans le chromosome est caractéristique de l’individu autant que du marqueur. Mais deux chromosomes différents comme

TAGACCACATAGGCGA

et

ATTAGCGCGGGGTTAG

bien que totalement différentes, ont deux fois le marqueur « TAG ». La fiabilité des tests d’ADN (qui sont basés sur des comptages de marqueurs dans plusieurs chromosomes) est basée sur les deux faits suivants :

  1. Si un marqueur est assez grand pour être rare sur le chromosome (par exemple TGCCACGT), la probabilité que le nombre d’apparition de ce marqueur soit le même chez deux individus différents est très faible.
  2. Sous réserve d’indépendance, les coïncidences simultanées du nombre de marqueurs sur plusieurs chromosomes chez deux individus différents sont encore moins probables.

Les questions mathématiques posées alors concernent la loi d’apparition d’une sous-chaîne de caractères dans un chromosome de plusieurs milliers, voire millions, de caractères, comme

  • Quelle est cette loi ?
  • Quelle est la probabilité d’une coïncidence (que la valeur de la variable aléatoire soit la même pour deux chaînes différentes) ?

Deux logiciels intéressants à examiner pour étudier l’ADN comme un langage sont blast et Biopython.

Remarque : La biotechnologie permettant de synthétiser de l’ADN, on peut imaginer que dans un futur proche, des informations, notamment des codes sources de logiciels, soient stockés dans de l’ADN (le risque de mutation génétique peut être compensé par un code correcteur d’erreurs style code de Golay). Faute de préparation juridique à cette technologie, il est envisageable que des brevets soient alors déposés sur de l’ADN. On se croira alors dans un de ces films de science-fiction où des mutants sont pourchassés pour leurs gènes, mais la brevetabilité du vivant permet déjà cette possibilité, comme le montre l’exemple de Monsanto. Voir à ce sujet cet article de Richard Stallman sur la biopiraterie.


Un autre domaine où la théorie des langages explique des phénomènes biologiques est la simulation de croissance de plantes par les grammaires L, mais un article entier sera consacré à ce sujet.

Informatique

c++, Pascal, Java (langage), Python, JavaScript sont des langages de programmation, donc a fortiori, des langages ! Décrire leur grammaire comme un ensemble de règles, fait appel à leur forme de Backus-Naur.

Si chaque fois qu’on utilise un fichier texte dans un programme, on considère qu’on utilise la théorie des langages, alors elle est utile

  • Chaque fois qu’on utilise un format vectoriel, comme avec InkScape (format svg) ou Asymptote (format postscript) ;
  • Chaque fois qu’on utilise un fichier xml, par exemple avec CaRMetal, Enigma ou GeoGebra...
  • Chaque fois qu’on navigue sur Internet (langages html, css et php),
  • Chaque fois qu’on lit ses mails (un mail est un fichier texte),
  • Chaque fois qu’on cherche un fichier, que ce soit avec un moteur de recherche (ce qu’on tape dedans est du texte !) ou sur l’ordinateur (le « finder » des Mac est dérivé d’un logiciel UNIX dont la version libre, grep, gère les RegExp) ;
  • Bien entendu, les logiciels éditeurs de texte manipulent des chaînes de caractère ; parmi ceux-ci, le logiciel cat (Unix) [1] a ceci de particulier que son nom même vient de l’opération de concaténation. Un programme est un fichier texte, donc en dernier ressort, programmer c’est manipuler des chaînes de caractères. Dans ce cas, la concaténation consiste à mettre l’une après l’autre deux instructions destinées à être exécutées en séquence, et elle est donc fondamentale en algorithmique. Lorsque un programme est en quelque sorte compilé et exécuté en même temps, le logiciel qui réalise ce prodige s’appelle un interpréteur, ce qui n’est pas un hasard...
  • Démarrer un programme ou naviguer dans le disque dur, ou gérer les « favoris » sont également des opérations sur les chaînes de caractère : Le lanceur (« Démarrer » sous Windows) est un fichier texte, les raccourcis et favoris sont des chaînes de caractère, et l’explorateur de fichier gère les chemins de ces fichiers, qui sont des chaînes de caractère (lisibles dans le rectangle en haut de la fenêtre).
  • Même démarrer l’ordinateur est souvent l’interprétation d’une chaîne de caractères (par exemple /boot/grub/menu.lst)...

String

Comme tous les langages objet, JavaScript gère les chaînes de caractère par le biais des objets String et RegExp. C’est JavaScript qui sera traité ici parce que conceptuellement, ce sont des chaînes de caractère qui sont produites par les CaRScripts. Voir à cet égard le tutoriel téléchargeable en pdf au bas de cette page.

Ainsi, même lorsqu’on fait ceci

var x=2+2;
Println(x);

c’est une chaîne de caractères qui est écrite et pas un nombre ; en effet « Println » ne sait imprimer que des chaînes de caractères ! Oui mais x est un nombre et pas une chaîne de caractères (sinon on aurait « 22 » au lieu de « 4 » puisque pour les chaînes, le signe « + » représente la concaténation) ! Aussi JavaScript réalise-t-il une conversion de x en chaîne de caractères, par

x.toString();

et du point de vue de l’interpréteur rhino, le script ci-dessus est discrètement transformé en

var x=2+2;
var affichage=x.toString();
Println(affichage);

La concaténation peut se faire soit comme une opération avec le signe « + », soit comme une méthode de l’objet String, méthode dont le nom est « concat ». Par exemple pour construire le mot « CaRMetal » à partir de « CaR » et « Metal », on a le choix entre les deux options suivantes :

var x="CaR"+"Metal";
var y="CaR".concat("Metal");

Pour savoir combien de caractères sont contenus dans une chaîne de caractères, on utilise sa propriété « length » :

Println("CaRMetal".length);

Pour accéder à une sous-chaîne, on donne les indices de départ et d’arrivée à la méthode « substring » de la chaîne :

var x="CaRMetal";
Println(x.substring(3,7));

À titre d’exemple, voici une implémentation itérative du test des palindromes (une fonction booléenne qui retourne « true » si le mot qu’on lui soumet est un palindrome, et « false » sinon) :

function reverse(s){
        var n=s.length;//savoir jusqu'où on boucle
        var chaine=new String();
        for(i=n-1;i>=0;i--){//on part de la fin
                caractere=s.substring(i+1,i);
                chaine+=caractere;
        }
        return(chaine);
}
function IsPalindrome(s){//fonction booléenne
        return(s==reverse(s));//un palindrome est une chaîne égale à son inverse
}
Println(IsPalindrome("abba"));

Par exemple, la fonction répondra « false » avec le mot « Laval » (pourquoi ?) et « true » avec l’expression « (11*11).toString() » (comment ?)

RegExp

Le travail des ribosomes commence par la recherche d’une sous-chaîne de caractères, ce qui peut se faire avec l’objet « String » en écrivant quelque chose comme ceci :

var s="Les poules couvent au couvent.";//la chaîne où on cherche un mot
for(i=0;i<=s.length;i++){
        if(s.substring(i,i+7)=="couvent"){
                Println(i);
        }
}

L’objet RegExp permet d’automatiser cette recherche, avec

var e=new RegExp(/couvent/);//le mot qu'on cherche
var s="Les poules couvent au couvent.";//la phrase où on cherche un mot
Println(s.match(e));

La réponse « couvent » signifie qu’une seule des deux occurences a été trouvée. Pour les trouver toutes, il faut donner à la RegExp l’attribut « global » qui cherche toutes les occurences :

var e=new RegExp(/couvent/g);//la regexp est globale, la recherche aussi
var s="Les poules couvent au couvent.";//la phrase où on cherche un mot
Println(s.match(e));

La réponse est en fait un tableau, dont la longueur donne le nombre d’occurences du mot « couvent » dans la phrase :

var e=new RegExp(/couvent/g);//la regexp est globale, la recherche aussi
var s="Les poules couvent au couvent.";//la phrase où on cherche un mot
Println(s.match(e).length);

Mais le plus intéressant avec les RegExp, c’est la possibilité de remplacer des sous-chaînes, une fois trouvées, par d’autres, pas nécessairement de la même longueur. Ceci se fait par la méthode « replace ». Par exemple pour mettre la phrase précédente au passé :

var e=new RegExp(/couvent/g);//la regexp est globale, la recherche aussi
var s="Les poules couvent au couvent.";//la phrase où on remplace un mot
Println(s.replace(e,"couvaient"));

La phrase obtenue est intéressante... Pour corriger l’erreur, il faut renoncer au remplacement global, et seulement mettre le premier « couvent » au passé :

var e=new RegExp(/couvent/);//la regexp n'est plus globale
var s="Les poules couvent au couvent.";//la phrase où on remplace un mot
Println(s.replace(e,"couvaient"));

Voilà, enfin les religieuses peuvent nourrir des poussins puisque les poules ont fini de couver !

Remarques

Seul l’aspect syntaxique de la théorie des langages a été abordé ici, la sémantique compliquant énormément les problèmes :

  1. L’exemple choisi pour illustrer les RegExp dans JavaScript montre que le même mot « couvent » peut avoir des sens bien différents selon le contexte (verbe au centre de la phrase, substantif à la fin de celle-ci). Il est connu que l’analyse syntaxique d’une phrase de langage parlé est indissociable de la sémantique, et de surcroît fortement dépendante du contexte. Dans le prochain article, on n’étudiera que les langages indépendants du contexte.
  2. Dans l’onglet sur les suites, l’usage des lettres « G » (comme « gauche ») et « D » (comme « droite ») n’était évidemment pas tout-à-fait innocent, et les langages définis dans cet onglet ont été créés avec l’idée d’une interprétation en tête.
  3. La numération est un langage plutôt simple, et évidemment il a une signification, en l’occurence basée sur la position. Les difficultés rencontrées par les enfants lorsqu’ils apprennent la numération peuvent donc in fine être considérées comme sémantiques.
  4. Le groupe décrit dans l’onglet « algèbre » par générateurs et relations est un groupe fondamental, auquel Poincaré avait trouvé une interprétation en terme de parcours de lacets.
  5. Si le décodage du génome est une activité essentiellement syntaxique, l’étude du repliement des protéines ressemble plus à de la sémantique, mais avec un niveau de complexité inimaginable...
  6. Enfin les langages de programmation réservent l’activité syntaxique à leur compilateur, l’aspect sémantique étant plutôt réservé à l’algorithmique (« que fait donc ce programme » ?)

Dans le prochain article, on se concentrera sur les langages les plus simples qui soient, et on leur cherchera des applications graphiques dans le troisième article, celui consacré aux grammaires L.


[1un des rares logiciels dont le nom peut être stocké dans de l’ADN, sous la forme Cytosine-Adénosine-Thymine !


Commentaires

Navigation

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


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

lundi 24 juillet 2017

Publication

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

Visites

51 aujourd'hui
427 hier
2064431 depuis le début
8 visiteurs actuellement connectés