Portal de Periódicos da CAPES

Transductions des langages de Chomsky

1968; Association of the Annals of the Fourier Institute; Volume: 18; Issue: 1 Linguagem: Francês

10.5802/aif.287

1777-5310

Maurice Nivat,

Advanced Algebra and Logic

La feuille des applications dites K-transductions, et qu'il serait légitime d'appeler applications rationnelles, d'un monoïde libre dans un autre monoïde est étudiée de façon systématique. L'intérêt de ces applications vient de ce qu'elles transportent partie algébrique (ou C-langages) sur partie algébrique, partie rationnelle (ou K-langage) sur partie rationnelle. On étudie sous le nom de langage compilable les parties algébriques qu'une K-transduction univoque applique dans un ensemble de Dyck (noyau d'un homomorphisme dans un groupe libre). On introduit la structure associative nouvelle de produit sélectif, aussitôt utilisée à la démonstration de l'équivalence de divers automates.