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.

Exemples

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

En combinatoire

Pour un alphabet ${\displaystyle \Sigma =\{x_{0},x_{1},...,x_{m}\}}$, muni de la fonction de taille ${\displaystyle \delta (x_{i})=i-1}$. Intuitivement, la lettre ${\displaystyle x_{i}}$ est un opérateur d'arité ${\displaystyle i}$. Les mots de Łukasiewicz sont les mots ${\displaystyle w_{1}\dots w_{\ell }}$ où ${\displaystyle w_{j}}$ est une lettre de l'alphabet ${\displaystyle \Sigma }$ tel que :

Pour tout ${\displaystyle \ell '<\ell }$, ${\displaystyle \sum _{j=1}^{\ell '}\delta (w_{j})\geq 0}$ et ${\displaystyle \sum _{j=1}^{\ell }\delta (w_{j})=-1}$.

Par exemple, un mot comme +1+23 s'écrit ${\displaystyle x_{2}x_{0}x_{2}x_{0}x_{0}}$. Comme

${\displaystyle {\begin{array}{ll}\delta (x_{2})&=1\geq 0,\\\delta (x_{2}x_{0})&=1-1\geq 0,\\\delta (x_{2}x_{0}x_{2})&=1-1+1\geq 0,\\\delta (x_{2}x_{0}x_{2}x_{0})&=1-1+1-1\geq 0,\\\delta (x_{2}x_{0}x_{2}x_{0}x_{0})&=1-1+1-1-1=-1\end{array}}}$

le mot ${\displaystyle x_{2}x_{0}x_{2}x_{0}x_{0}}$ est un mot de Łukasiewicz.

Ces mots codent les arbres plans^[1].

En théorie des langages formels

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 : (${\displaystyle x_{0}}$ d'arité 0 et ${\displaystyle x_{2}}$ d'arité 2). Il est engendré par la grammaire formelle suivante :

${\displaystyle S\to x_{2}SS\mid x_{0}}$

On rencontre souvent l'écriture plus simple:

${\displaystyle S\to aSS\mid b}$,

avec ${\displaystyle a=x_{2}}$ et ${\displaystyle b=x_{0}}$. Plus généralement, la grammaire

${\displaystyle S\to x_{n}S^{n}\mid x_{n-1}S^{n-1}\mid \cdots \mid x_{2}S^{2}\mid x_{1}S\mid x_{0}}$

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

${\displaystyle S\to \sum _{i\in I}x_{i}S^{i}\mid x_{0}}$.

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

Propriétés

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

• Notation polonaise ou Notations infixée, préfixée et postfixée

Notes et références

• Portail de l'informatique théorique
• Portail des mathématiques