SemiautomatonIn 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.
Système de transition d'étatsEn informatique théorique, un système de transition d'états est une forme de machine abstraite utilisée pour modéliser un ou des calcul(s). Un système de transition d'états est constitué d'un ensemble d'états et d'un ensemble de transitions d'un état à un autre, qui peuvent être étiquetées ; une même étiquette peut apparaître sur plusieurs transitions. Si l'ensemble des étiquettes est un singleton, on peut omettre l'étiquetage. Les systèmes d'états-transitions sont des graphes orientés.
Théorie des représentationsLa théorie des représentations est une branche des mathématiques qui étudie les structures algébriques abstraites en représentant leurs éléments comme des transformations linéaires d'espaces vectoriels, et qui étudie les modules sur ces structures algébriques abstraites. Essentiellement, une représentation concrétise un objet algébrique abstrait en décrivant ses éléments par des matrices et les opérations sur ces éléments en termes d'addition matricielle et de produit matriciel.
Automate fini déterministeUn automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.
Automate finithumb|upright=2|Fig. 1 : Une hiérarchie d'automates. Un automate fini ou automate avec un nombre fini d'états (en anglais finite-state automaton ou finite state machine ou FSM) est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie.
MonoïdeEn mathématiques, un monoïde est une structure algébrique utilisée en algèbre générale, définie comme un ensemble muni d'une loi de composition interne associative et d'un élément neutre. Autrement dit, c'est un magma associatif et unifère, c'est-à-dire un demi-groupe unifère. Il arrive parfois qu'une structure composée d'un ensemble et d'une unique opération soit relativement pauvre en éléments inversibles, par exemple un anneau où l'on considère uniquement la multiplication. Une telle structure est appelée monoïde.
Demi-groupeEn mathématiques, plus précisément en algèbre générale, un demi-groupe (ou semi-groupe) est une structure algébrique constituée d'un ensemble muni d'une loi de composition interne associative. Il est dit commutatif si sa loi est de plus commutative. Un demi-groupe est un magma associatif. Un monoïde est un demi-groupe unifère, c'est-à-dire possédant un élément neutre. L'ensemble des entiers naturels non nuls muni de l'addition est un demi-groupe. Tout monoïde est un demi-groupe. Tout groupe est un demi-groupe.
