APPLICATIONS GEOMETRIQUES DES LANGAGES FORMELS - REGULAR FEATURES

Sep 29, 2026

Télécharger par Anna Hans

Travaux sur la connexion entre grammaires formelles et objets géométriques via des méthodes issues de la théorie des langages formels. L’article propose des exemples de grammaires de Chomsky capables d’engendrer des figures géométriques simples, puis indique comment, en ne retenant que certains paramètres, on obtient des fonctions génératrices classiques. Il discute aussi l’obtention d’énumérations de figures plus compliquées par des techniques standards, en s’appuyant sur des suggestions et relectures de collègues mentionnés dans le texte.

LangueFrench

CatégorieRecherche & Rapport

FormatPDF

Pages80

Temps de lecture2 h 3 min

AccèsTéléchargement gratuit

Table des matières

I. GRAMMAIRES ET LANGAGES DE CHOMSKY

1)Definitions Genérales

2)Exemple de C-Langage

ly-September 1966Volume 5,No.3me(C去).2ematen Cnoutatan cCante CCBULLETII CONTENTS plications géométriques des langages formels Conjecture concerning Non-Context-FreeLanguages M.Gross G.H.Matthews EGULAR FEATURES ws of Computing Laboratories andUniversities ws of International Organizationsview of Computersok Reviews INTERNATIONAL COMPUTATION CENTRECENTRE INTERNATIONAL DECALCUL J.Abadie(France) E.Sparre Andersen (Denmark)R.Bellman (USA) F.L.Bauer(Germany)S.F.Beltran(Mexico) C.Berge(ICC) C.Blanc(Switzerland) C.Böhm(Italy) E.R.Caianello(Italy)S.Comét (Sweden) H.B.Curry(USA) B.de Finetti(Italy)R.de Possel (France)P.Erdós(Hungary) A.P.Ershov(USSR)R.Fortet (France) F.Genuys(France) A.Ghizzetti(Italy)P.Gillis(Belgium)V.Glushkov(USSR) G.Hajós(Hungary) A.J.Hoffman(USA) L.Karp(Mexico)S.H.Khamis(Lebanon) H.Kneser(Germany) K.Kondo(Japan) dell'E.U.R.,Rome.Cable address:INTERCALCOLO. # I.C.C.BULLETIN EDITORIAL BOARD H.Kuhn(USA) M.Linsman(Belgium) J.L.Lions(France) F.Loonstra(Netherlands) L.Lukaszewicz(Poland)R.McNaughton(USA)S.Marcus(Rumania) C.Moisil (Rumania)O.Morgenstern (USA)S.Moriguti(Japan)R.Narasimhan(India) J.Neveu(Belgium) A.M.Ostrowski(Switzerland) M.Rabin(Israel)P.Rabinowitz(Israel) A.Renyi(Hungary) M.Sadosky(Argentina) M.P.Schützenberger(France) L.Schmetterer(Austria)S.J.Shepherdson (UK) H.Takahasi(Japan)O.Taussky Todd (USA)S.Ulam(USA)P.Wolfe(USA) F.Yates(UK) The opinions expressed in signed articles in the ICC Bulletin are those of the authorsand do not necesarily represent the views of the International Computation Centre. The ICC Buletin,accepts articles in English and French,and is published quarterlyby Gordon and Breach,Science Publishers,Ltd. Subscribtion rate:Libraries $15.00(5.5s),Individuals S7.50(2.12s).Subscriptionsshould be sent to Gordon and Breach,Science Publishers,Ltd.,9 Kingsway,London,W.C.2,England. Ediorial Ofice:International Computation Centre,Casella postale No.10053,Zona # APPLICATIONS GEOMETRIQUESDES LANGAGES FORMELS¹ MAURICE GROSs Centre National de la Recherche Scientifique,Laboratoire de Calcul Numerique,Institut Blaise Pascal,Paris DANS certains problemes combinatoires d'énumération on obtient lenombre de certains objets ayant certaines caractéristiques (nombre desC-arbres ayant n aretes)au moyen d'une fonction génératrice.M.P.Schützenberger nous a suggéré que ces fonctions de variables commu-tatives devraient pouvoir s'obtenir à partir de fonctions de variablesnon-commutatives qui dans le cas des fonctions algébriques au sens deSchützenberger s'identifient à certaines classes importantes des gram-maires formelles. Nous donnons ici des exemples de grammaire de Chomsky quiengendrent des figures géométriques simples,quand on ne retient de cesfigures que certains parametres,on obtient les fonctions génératricesclassiques. Des techniques standards de la théorie des langages formels permet-tent d³obtenir des énumérations de figures compliquées. Nous sommes redevables à M.P.Schützenberger de nombreusessuggestions età A.Lentin d'avoir relu notre manuscrit et d'en avoiréclairci certains points. ## I.GRAMMAIRES ET LANGAGES DE CHOMSKY² ### 1)Definitions Genérales Ce sont des systemes qui définissent certaines sous-classes du monoidelibre.Nous rappellerons ici leur définition,pour des descriptionsprécises voir Chomsky,Chomsky et Schützenberger. 1 Manuscript recu le 29.11.65. 2 En anglais:context-free grammar,context-free language.Nous utiliserons lesabréviations:C-grammaire et C-langage. M.GROSs Soitun ensembleVr={a;},que nous appellerons vocabulaire terminal,Vr comporte les lettres a;;soit F(VT)le monoide libre engendré parVT,c³est Iensemble des mots sur les a;nous appellerons langage toutensemble LcF(VT). Pour realiser Pénumération effective d³un langage c'est-à-dire pourengendrer ce langage,nous utiliserons une grammaire qui est unespecification récursive de ce langage.Pour définir une gramm

FAQ

Comment l’article définit-il une grammaire et le langage qu’elle engendre ?

Une grammaire est un ensemble fini de règles de réécriture à partir d’un axiome, et le langage associé correspond à l’ensemble des mots obtenus par applications successives des règles en commençant par l’axiome.

Sep 29, 2026

Télécharger par Anna Hans