Monoïde syntaxique

En informatique théorique, et en particulier dans la théorie des automates finis, le monoïde syntaxique d'un langage formel est un monoïde naturellement attaché au langage. L'étude de ce monoïde permet de refléter certaines propriétés combinatoires du langage par des caractéristiques algébriques du monoïde. L'exemple le plus célèbre de cette relation est la caractérisation, due à Marcel-Paul Schützenberger, des langages rationnels sans étoile (que l'on peut décrire par des expressions rationnelles avec complément mais sans l'étoile de Kleene) : ce sont les langages dont le monoïde syntaxique est fini et apériodique, c'est-à-dire ne contient pas de sous-groupe non trivial. Soit un langage sur un alphabet , soit un monoïde et soit un morphisme de dans . On dit que le morphisme reconnaît si et seulement si il existe une partie de telle que . On dit qu'un monoïde reconnaît s'il existe un morphisme qui reconnaît . On a les résultats suivants : Si un monoïde reconnaît un langage et est un sous monoïde de , alors reconnaît . Si un monoïde reconnaît un langage et est quotient de , alors reconnaît . Si un monoïde reconnaît un langage et divise , alors reconnaît . Étant donné un langage formel sur l'alphabet , deux mots u et v sont dits syntaxiquement équivalents si tout mot w du langage dont u est un facteur donne un mot qui est encore dans le langage si on remplace l'occurrence de u par v. Formellement, le contexte d'un mot est l'ensemble des couples de mots tels que . Deux mots u et v sont syntaxiquement équivalents s'ils ont même contexte, soit Cette équivalence est en fait une congruence de monoïde, c'est-à-dire compatible à gauche et à droite avec la multiplication. Le quotient de l'ensemble des mots par la relation est un monoïde, appelé le monoïde syntaxique de . Le morphisme de sur ce monoïde qui à un mot associe sa classe est le morphisme syntaxique. Le langage est saturé pour la congruence syntaxique, c'est-à-dire qu'il est union de classes de la congruence syntaxique.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (7)

Concepts associés (11)

Cours associés (1)

Séances de cours associées (14)

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

Demi-groupe de transformations

En algèbre, un demi-groupe de transformations est un ensemble de fonctions d'un ensemble X dans lui-même qui est fermé pour l'opération de composition. S'il contient l'application identité, c'est un monoïde de transformations. C'est l'analogue, pour les demi-groupes, d'un groupe de permutations. Un analogue du théorème de Cayley vaut pour les demi-groupes : tout demi-groupe est isomorphe à un demi-groupe de transformations sur un ensemble. Un demi-groupe de transformations est un couple , où est un ensemble, et est un demi-groupe de transformations sur .

Semiautomaton

In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function. Associated with any semiautomaton is a monoid called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states Q.

String operations

In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms. A string is a finite sequence of characters. The empty string is denoted by . The concatenation of two string and is denoted by , or shorter by . Concatenating with the empty string makes no difference: .

The algebra of Boolean matrices, correspondence functors, and simplicity

Jacques Thévenaz, Serge Bouc

We determine the dimension of every simple module for the algebra of the monoid of all relations on a finite set (i.e. Boolean matrices). This is in fact the same question as the determination of the dimension of every evaluation of a simple correspondence ...

2020

An improvement on the number of simplices in F-q(d)

Van Thang Pham

Let epsilon be a set of points in F-q(d). Bennett et al. (2016) proved that if \epsilon\ >> [GRAHICS] then epsilon determines a positive proportion of all k-simplices. In this paper, we give an improvement of this result in the case when epsilon is the Car ...

Elsevier Science Bv2017

Polarization and Channel Ordering: Characterizations and Topological Structures

Rajai Nasser

Information theory is the field in which we study the fundamental limitations of communication. Shannon proved in 1948 that there exists a maximum rate, called capacity, at which we can reliably communicate information through a given channel. However, Sha ...

EPFL2017

Langages formels : Concepts CS-320: Computer language processing

Couvre les concepts fondamentaux des langues formelles, y compris les alphabets, les mots, les langues et l'égalité des mots.

Langages formels : Concepts CS-320: Computer language processing

Couvre les bases des langues formelles, y compris les alphabets, les mots et les langues, ainsi que des opérations comme la concaténation et l'inversion.

Algèbre abstraite et classes de type CS-210: Functional programming

Couvre les concepts d'algèbre abstraite en utilisant des classes de type dans Scala, y compris la définition des monoïdes, la généralisation des fonctions de réduction et les lois de classe de type.