Accueil🇫🇷Chercher

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 , 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

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

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

Notes et références

  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]).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.