Automates et langages formels I – La numération de Zeckendorf

Dans le billet précédent, on a construit, pour toute base b et tout diviseur d, un graphe avec lequel on peut déterminer très facilement le reste modulo d d’un nombre à partir de son expression en base b. Ce graphe est un exemple d’automate fini déterministe.

Les automates finis déterministes forment une vaste famille d’outils à l’aide desquels on peut analyser commodément la syntaxe de nombreux langages — les plus « simples » au sens de la hiérarchie de Chomsky.

Je me propose de donner quelques définitions relatives aux langages formels et aux automates (déterministes) avant de présenter certains résultats concernant les automates finis déterministes et les langages associés, ceci au fil de plusieurs billets.

Langages

Un langage est, en ce qui nous concerne, un ensemble de mots et un mot est une suite finie de symboles — on dit ses lettres — pris dans un ensemble fini, fixé une fois pour toute : l’alphabet du langage.

Les chiffres en base 10 forment l’alphabet de la numération décimale. Chaque nombre entier positif est représenté par un mot sur cet alphabet et l’ensemble des mots représentant ces nombres est ce qu’on appelle le langage de la numération (de position) en base 10. Il s’agit de l’ensemble formé de 0 et des suites de chiffres 0,…,9 ne commençant pas par 0.

Plus généralement, un système de numération est une manière de représenter chaque nombre(*) par un mot en établissant une bijection entre \mathbb N et un langage sur un certain alphabet. Les systèmes de numération de position, utilisant une base entière b, sont sans doute les plus connus. Dans ce cas l’alphabet est l’ensemble \{0,1,...,b-1\} des restes modulo b. Outre le système de base 10, universellement répandu, il y a par exemple le système binaire, popularisé par l’informatique.

Il y a bien d’autres systèmes de numération et j’aurai l’occasion de revenir sur la notion et d’en présenter quelques uns, plus exotiques.

Une autre famille de langages, que nous devons aussi à l’informatique, est celle des langages de programmation. Grossièrement parlant, les mots d’un tel langage sont, en plus des identificateurs et des instructions de base, les programmes qu’on peut rédiger dans ce langage.

Un problème fondamental de la théorie des langages formels consiste à reconnaître si un mot donné construit sur un l’alphabet d’un langage appartient ou non à celui-ci. Nombres de problèmes peuvent être modélisés en ces termes — en fait, tous ceux faisant l’objet de ce qu’on appelle la théorie de la calculabilité — et une question centrale consiste à étudier les algorithmes permettant de décider de l’appartenance d’un mot à un langage.

La sophistication d’un tel algorithme dépend naturellement de la structure du langage qu’il permet d’analyser. Les plus sophistiqués sont les machines de Turing; les plus élémentaires sont les automates finis. Deux familles supplémentaires d’algorithmes décrivent des niveaux de complexités intermédiaires. Ils forment avec les deux premières, ce qu’on appelle la hiérarchie de Chomsky.

La plupart des systèmes de numérations sont construits sur un langage décidable par un automate fini. A quelques caractéristiques près, les langages de programmation appartiennent généralement au niveau immédiatement supérieur de la hiérarchie, l’essentiel de leurs règles grammaticales étant, ainsi qu’on le dit, non contextuelles.

Concaténation

L’ensemble des mots sur un alphabet est muni d’une opération particulièrement utile, la concaténation. Elle permet d’étudier les langages formels à l’aide des ressources de l’algèbre.

Naïvement, la concaténation de deux mots u,v est leur juxtaposition uv. Elle est associative et possède un élément neutre, le mot vide, communément noté \varepsilon(**).

Voyons les choses d’un point de vue plus formel.

Par définition, les mots de longueur n\in\mathbb N sur un alphabet A sont, pour n>0, les éléments du produit cartésien A^n de n copies de A. On pose A^0=\{\varepsilon\}. La concaténation est alors définie sur l’ensemble

A^*=\bigcup\limits_{n\in\mathbb N}A^n

de tous les mots sur l’alphabet A par

(u=(a_1,...,a_m),v=(b_1,...,b_n))\mapsto uv:=(a_1,...,a_m,b_1,...,b_n)

et \varepsilon u=u\varepsilon =u. Par construction, elle est associative et le mot vide en est une unité. En particulier,

(a_1,...,a_m)=a_1\cdots a_m

et c’est en juxtaposant de la sorte ses composantes que nous représenterons le plus souvent un mot.

La concaténation s’étend aux langages. La concaténation de L,M\subset A^* est le langage :

LM=\{uv|u\in L,v\in M\}

Couplée avec les opérations ensemblistes usuelles, elle permet de construire de nombreux langages (nous verrons exactement lesquels plus tard). Par exemple,

\{0\}\cup\{1,2,3,4,5,6,7,8,9\}\{0,1,2,3,4,5,6,7,8,9\}^*

est le langage de la numération de position en base 10.

Combinée en particulier avec l’union, la concaténation des langages donne lieu à une opération fondamentale, l’étoile de Kleene, décrite au paragraphe suivant.

Etoile de Kleene

Par définition, l’étoile de Kleene L^* d’un langage L\subset A^* est l’ensemble des concaténations d’un nombre arbitraire d’éléments de L. En convenant de noter exponentiellement les concaténations de plusieurs copies de L :

L^0=\{\varepsilon\}, L^1=L, L^2=LL, L^3=L^2L,...

on peut donc écrire L^*=\bigcup_{n\in\mathbb N}L^n. Ceci n’est pas contradictoire avec la notation adoptée pour désigner l’ensemble des mots sur l’alphabet A car c’est précisément l’étoile de Kleene de ce dernier.

A titre d’exemple, voici une description des mots sur \{0,1\} comportant un nombre pair de 1 :

(\{0\}\cup\{1\}\{0\}^*\{1\})^*

On écrit cela plus simplement en convenant de supprimer les accolades lorsqu’elles n’entourent qu’un mot : (0\cup 10^*1)^*.

Un exemple : la numération de Zeckendorf

E. Zeckendorf a découvert une propriété des nombres de Fibonacci qui débouche sur un système de numération appartenant à une vaste famille de systèmes, connus sous le noms de « systèmes de A. Bertrand ». Voici les détails.

La suite des nombres de Fibonacci est définie par récurrence par la relation

F_{k+2}=F_{k+1}+F_k

et la condition initiale F_1=F_2=1.

D’après Zeckendorf(***), tout entier positif s’écrit de manière unique comme une somme de nombres de Fibonacci d’indices plus grands que 1 et deux à deux non consécutifs. C’est à cause de la condition initiale de la suite de Fibonacci qu’on demande que les indices de la décomposition soient plus grands que 1. Sans cela, l’unicité de la décomposition ne serait pas assurée.

La décomposition d’un entier positif n>0 est facile à obtenir : la suite de Fibonacci étant strictement croissante à partir du rang 2, il existe un entier k\geq 2 tel que

F_k\leq n<F_{k+1}

On retient l’indice k. Si n= F_k, la décomposition est achevée. Sinon, on recommence avec n-F_k.
Par exemple, ce procédé fournit la décomposition suivante de 72

72=F_{10}+F_7+F_4+F_2

Le système de numération associé est la numération de Zeckendorf. Il consiste à représenter un entier n par 0 s’il est nul, et par une suite u_k\cdots u_1 de 1 et de 0 dans laquelle u_j vaut 1 si F_{j+1} figure dans la décomposition de n et est nul sinon. Par convention, la suite débute, à gauche, par un 1, ce qui en détermine la longueur. La représentation de 72 est ainsi 100100101.

Je vous propose de décrire le langage de la numération de Zeckendorf à l’aide de l’union, de la concaténation et de l’étoile de Kleene.😉

P.S. Une solution est donnée dans ce billet. PL, le 21 juin 2011.
__________
(*) Il s’agit d’abord de représenter les entiers positifs ou nuls puis d’étendre éventuellement le système aux réels, puis aux complexes, etc.
(**) Par contre aucun mot non vide n’admet d’inverse. L’ensemble des mots sur un alphabet n’est donc pas un groupe pour la concaténation mais bien ce qu’on appelle un monoïde.
(***) Zeckendorf, E. Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s