Langage de Łukasiewicz

(Redirigé depuis Langage de Lukasiewicz)

En informatique théorique, plus précisément en théorie des langages formels et en combinatoire, le langage de Łukasiewicz (ou langage des expressions en notation polonaise) est le langage des expressions préfixes, c'est-à-dire où l'opérateur précède les arguments. Il porte le nom de Jan Łukasiewicz.

Exemples modifier

Au lieu d'écrire des expressions comme 1+2 où l'opérateur + est en position infixe, on écrit +12. Les mots comme +12, +1+23 sont des mots du langage de Łukasiewicz. Par exemple, on écrit ×5+34 au lieu de 5 × (3 + 4).

Définitions modifier

En combinatoire modifier

Pour un alphabet , muni de la fonction de taille . Intuitivement, la lettre est un opérateur d'arité . Les mots de Łukasiewicz sont les mots est une lettre de l'alphabet tel que :

Pour tout , et .

Par exemple, un mot comme +1+23 s'écrit . Comme

le mot est un mot de Łukasiewicz.

Ces mots codent les arbres plans[1].

En théorie des langages formels modifier

En théorie des langages, le langage de Łukasiewicz est engendré par une grammaire algébrique[2]. Commencons par l'exemple du langage de Łukasiewicz avec deux lettres : ( d'arité 0 et d'arité 2). Il est engendré par la grammaire formelle suivante :

On rencontre souvent l'écriture plus simple:

,

avec et . Plus généralement, la grammaire

correspond au langage de Łukasiewicz donné plus haut où la lettre est un opérateur d'arité . On peut aussi ne choisir qu'une partie des symboles , comme dans la première définition par grammaire où seulement et interviennent. On a alors la version la plus générale : soit un sous-ensemble non vide de . Alors le langage est donné par la grammaire

.

Il y a un lien étroit entre le langage de Łukasiewicz et le langage de Dyck.

Propriétés modifier

Du point de vue des langages formels, un langage de Łukasiewicz est un langage algébrique inambigu. C'est aussi un code préfixe, c'est-à-dire ayant la propriété qu'aucun mot du langage n'est un préfixe d'un autre mot du langage.

Quant aux propriétés combinatoires, elles sont nombreuses, et s'expliquent par le rapport avec les propriétés des arbres.

Plus familière est la notation postfixée qui s'obtient par retournement de la notation préfixée. Cette notation était utilisée dans les toutes premières calculettes ; elle est encore à la base de certains langages de programmation, comme le langage PostScript.

Article connexe modifier

Notes et références modifier

  1. (en) Richard Stanley, Hipparchus, Plutarque, Schröder and Hough, (lire en ligne [PDF]).
  2. Rémi Eyraud, Inférence grammaticale de langages hors-contextes, (lire en ligne [PDF]).