Grammaires II régulières II
En prenant S comme axiome, une grammaire possible de génération d'une séquence
d'ARN bactérien codant pour une protéine est la suivante :
{1 :S-+ aX,, 2 : X, -+ uX:,1 3: X 2 -+ gX) U {4 :X 3 -+ aX 4 , 5: X
7
-+ aX 4 I a E {a,c,g}} U { 6 :
X4-+ px6' 7 : X 6-+ p x 7 1 p E {a, c, g, u}} u { 8 : X 5-+ yX 6' 9: X B-+ yX 7 1 y E {c, g, u}} u
{ 10 : x3-+ uX5, 11 : X 7-+ uX5, 12 : X 5-+ aXB, 13 : X B-+ a}.
Elle pourra par exemple générer la séquence augccguaa en utilisant successivement les
règles 1, 2 et 3 (aug) , puis 4, 6 et 7 (ccg) , et enfin 11, 12 et 13 (uaa). Observez que la structure des règles est très régulière : elles sont toutes de la forme « un non terminal se récrit
en un symbole terminal suivi éventuellement d'un non terminal » . On nomme réguliers
les langages générés avec cette forme de règles. Ces langages ont une foule de bonnes
propriétés qui en font un outil précieux en informatique (système Unix, traitements de
texte ... ). Ainsi, savoir si une phrase appartient à un langage régulier demande un nombre
d'opérations proportionnel à la taille de la phrase. De plus ils forment une classe stable au
sens où l'intersection, l'union, le complémentaire, la différence ou l'application d'un homomorphisme sur un langage régulier continuent à donner un langage régulier.
Les langages peuvent aussi être décrits, de façon équivalente, à l'aide de machines : c'est
un modèle plus proche de ce qui se passe en biologie où de nombreuses machines sont en
œuvre ainsi qu'en informatique où on définit plusieurs types de machines abstraites en
fonction du type de langages, la plus générale, la machine de Turing, étant le fondement
de nos ordinateurs.
Pour reconnaître un langage régulier, on utilise ainsi ce qu'on appelle des automates
d'états finis. La machine part d'un état initial et lit les symboles de la phrase de gauche
à droite. En utilisant une fonction de transition fixée qui associe à chaque état et chaque
symbole lu un nouvel état, la machine progresse tant que c'est possible d'états en états.
La phrase est reconnue si la machine termine dans un état final. On représente graphiquement les états par des cercles, un état final par un double cercle et une transition en
lisant un symbole par une flèche depuis l'état de départ jusqu'à l'état d'arrivée surmontée
du symbole. Nous effleurons juste en passant la notion de probabilité qu'on peut introduire dans les langages et leurs représentations: rien n'empêche de considérer un langage
comme une distribution de probabilités sur l'ensemble des enchaînements possibles. D'un
point de vue grammaire ou machine, ceci suppose d'associer des probabilités aux règles
ou aux transitions. Nous nous contentons ici de considérer que toutes les phrases ont la
probabilité o ou 1. En pratique, il peut exister en biologie différentes alternatives d'analyse
(on parle d'ambiguïté) avec des probabilités différentes pour de mêmes phrases, comme
par exemple dans le cas des télomérases qui oscillent entre deux états stables.
l\ insi, une grammaire ho rs contexte
)Our la reconnaissance de ti ges-bo ucles
fa ns I 'ARN peut être décrit par deux
!nsembles de règles (l' un pour la tige,
le deuxième pour la boucle) :
{S-+ aSu , S-+ cSg, S-+ gSc, S-+ uSa}
U { S-+ aX, X-+ a l a E {a,c,g, t} }.
De même, il fa ut amé liorer la machine
précédente en ajoutant une mé mo ire
Hors-série n°52. L'informatique Tangente
En prenant S comme axiome, une grammaire possible de génération d'une séquence
d'ARN bactérien codant pour une protéine est la suivante :
{1 :S-+ aX,, 2 : X, -+ uX:,1 3: X 2 -+ gX) U {4 :X 3 -+ aX 4 , 5: X
7
-+ aX 4 I a E {a,c,g}} U { 6 :
X4-+ px6' 7 : X 6-+ p x 7 1 p E {a, c, g, u}} u { 8 : X 5-+ yX 6' 9: X B-+ yX 7 1 y E {c, g, u}} u
{ 10 : x3-+ uX5, 11 : X 7-+ uX5, 12 : X 5-+ aXB, 13 : X B-+ a}.
Elle pourra par exemple générer la séquence augccguaa en utilisant successivement les
règles 1, 2 et 3 (aug) , puis 4, 6 et 7 (ccg) , et enfin 11, 12 et 13 (uaa). Observez que la structure des règles est très régulière : elles sont toutes de la forme « un non terminal se récrit
en un symbole terminal suivi éventuellement d'un non terminal » . On nomme réguliers
les langages générés avec cette forme de règles. Ces langages ont une foule de bonnes
propriétés qui en font un outil précieux en informatique (système Unix, traitements de
texte ... ). Ainsi, savoir si une phrase appartient à un langage régulier demande un nombre
d'opérations proportionnel à la taille de la phrase. De plus ils forment une classe stable au
sens où l'intersection, l'union, le complémentaire, la différence ou l'application d'un homomorphisme sur un langage régulier continuent à donner un langage régulier.
Les langages peuvent aussi être décrits, de façon équivalente, à l'aide de machines : c'est
un modèle plus proche de ce qui se passe en biologie où de nombreuses machines sont en
œuvre ainsi qu'en informatique où on définit plusieurs types de machines abstraites en
fonction du type de langages, la plus générale, la machine de Turing, étant le fondement
de nos ordinateurs.
Pour reconnaître un langage régulier, on utilise ainsi ce qu'on appelle des automates
d'états finis. La machine part d'un état initial et lit les symboles de la phrase de gauche
à droite. En utilisant une fonction de transition fixée qui associe à chaque état et chaque
symbole lu un nouvel état, la machine progresse tant que c'est possible d'états en états.
La phrase est reconnue si la machine termine dans un état final. On représente graphiquement les états par des cercles, un état final par un double cercle et une transition en
lisant un symbole par une flèche depuis l'état de départ jusqu'à l'état d'arrivée surmontée
du symbole. Nous effleurons juste en passant la notion de probabilité qu'on peut introduire dans les langages et leurs représentations: rien n'empêche de considérer un langage
comme une distribution de probabilités sur l'ensemble des enchaînements possibles. D'un
point de vue grammaire ou machine, ceci suppose d'associer des probabilités aux règles
ou aux transitions. Nous nous contentons ici de considérer que toutes les phrases ont la
probabilité o ou 1. En pratique, il peut exister en biologie différentes alternatives d'analyse
(on parle d'ambiguïté) avec des probabilités différentes pour de mêmes phrases, comme
par exemple dans le cas des télomérases qui oscillent entre deux états stables.
l\ insi, une grammaire ho rs contexte
)Our la reconnaissance de ti ges-bo ucles
fa ns I 'ARN peut être décrit par deux
!nsembles de règles (l' un pour la tige,
le deuxième pour la boucle) :
{S-+ aSu , S-+ cSg, S-+ gSc, S-+ uSa}
U { S-+ aX, X-+ a l a E {a,c,g, t} }.
De même, il fa ut amé liorer la machine
précédente en ajoutant une mé mo ire
Hors-série n°52. L'informatique Tangente