Langage de Łukasiewicz

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.

ExemplesModifier

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éfinitionsModifier

En combinatoireModifier

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 formelsModifier

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ésModifier

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 connexeModifier

Notes et référencesModifier

  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]).