Colloque

Machines séquentielles et langages formels

Claude Boucher

Membre a labase

Claude Boucher

Résumé du colloque

On étudie divers types de machines séquentielles et les propriétés de fermeture des langages réguliers et indépendants de contexte par rapport à ces machines. Le principal résultat concerne les machines séquentielles de type m - n; on appelle ainsi un 7-tuplet M = (K, Σ, Δ, Ms0, (Si)1 ≤ i ≤ m, (Sj')1 ≤ j ≤ n) où K, Σ et Δ sont des ensembles finis, μ une application de K x Σ dans K x θ(Δ), s0 un élément distingué de K et (Si)1 ≤ i ≤ m, (Sj')1 ≤ j ≤ n des partitions de K. Une telle machine permet de faire correspondre à un m-tuplet (Li)1 ≤ i ≤ m de parties de θ(Σ) un n-tuplet (Li')1 ≤ j ≤ n de parties de θ(Δ). On montre que si tous les Li sont des langages réguliers (resp. sont des langages réguliers sauf un qui est indépendant de contexte), alors tous les Li' sont des langages réguliers (resp. sont des langages indépendants de contexte).

Contexte

Section :

Mathématiques A: algèbre logique

Thème du colloque :

Mathématiques A: algèbre logique

Hôte : Université de Montréal

Découvrez d'autres communications scientifiques

Dans le même colloque
Du même congressiste

Titre du colloque :

Mathématiques A: algèbre logique

Catégories fibrées et catégories ayant assez de localisations

S. Takahashi

Machines séquentielles et langages formels

Claude Boucher

Un théorème de réalisation pour certains demi-groupes

F.-P. Gagnon

Voir tous les contenus de ce colloque

Autres communications du même congressiste :

Thème du colloque :

Mathématiques A: algèbre logique

Diagnostics pour l'étude de la production et du transport des impuretés dans le Tokamak de Varennes

Bernard Terreault

Système à vide, de mesure et de contrôle de pression dans le Tokamak de Varennes

Claude Boucher

Comportement des getters frais au Zr-V-Fe exposés à l'hydrogène dans un système ultra haut vide

Claude Boucher