Semiautónomo

En matemáticas e informática teórica , un semiautómata es un autómata finito determinista que tiene entradas pero no salida. Consta de un conjunto Q de estados , un conjunto Σ llamado alfabeto de entrada y una función T : Q × Σ → Q llamada función de transición.

Todo semiautómata está asociado a un monoide llamado monoide característico , monoide de entrada , monoide de transición o sistema de transición del semiautómata, que actúa sobre el conjunto de estados Q. Esto puede verse como una acción del monoide libre de cadenas en el alfabeto de entrada Σ, o como el semigrupo de transformación inducido de Q.

En libros más antiguos, como los de Clifford y Preston (1967), las acciones de semigrupo se denominan "operandos".

En teoría de categorías , los semiautómatas son esencialmente functores .

Un semigrupo de transformación o monoide de transformación es un par${\displaystyle (M,Q)}$Consiste en un conjunto Q (a menudo llamado "conjunto de estados ") y un semigrupo o monoide M de funciones , o "transformaciones", que mapean Q en sí mismo. Son funciones en el sentido de que cada elemento m de M es una función.${\displaystyle m\colon Q\to Q}$Si s y t son dos funciones del semigrupo de transformación, su producto de semigrupos se define como su composición de funciones.${\displaystyle (st)(q)=(s\circ t)(q)=s(t(q))}$.

Algunos autores consideran "semigrupo" y "monoide" como sinónimos. En este contexto, un semigrupo no necesariamente tiene un elemento neutro ; un monoide es un semigrupo con un elemento neutro (también llamado "unidad"). Dado que la noción de funciones que actúan sobre un conjunto siempre incluye la noción de función identidad, la cual, al aplicarse al conjunto, no produce ningún efecto, un semigrupo de transformación puede convertirse en un monoide añadiéndole la función identidad.

Un semiautómata es un triple${\displaystyle (Q,\Sigma ,T)}$dónde${\displaystyle \Sigma }$es un conjunto no vacío, llamado alfabeto de entrada , Q es un conjunto no vacío, llamado conjunto de estados , y T es la función de transición.

${\displaystyle T\colon Q\times \Sigma \to Q.}$

Cuando el conjunto de estados Q es un conjunto finito —aunque no necesariamente lo es—, un semiautómata puede considerarse como un autómata finito determinista.${\displaystyle (Q,\Sigma ,T,q_{0},A)}$pero sin el estado inicial${\displaystyle q_{0}}$o conjunto de estados de aceptación A. Alternativamente, es una máquina de estados finitos que no tiene salida, y solo una entrada.

Cualquier semiautómata induce un acto de un monoide de la siguiente manera.

Dejar${\displaystyle \Sigma ^{*}}$sea ​​el monoide libre generado por el alfabeto${\displaystyle \Sigma }$(de modo que el superíndice * se entiende como la estrella de Kleene ); es el conjunto de todas las cadenas de longitud finita compuestas por las letras en${\displaystyle \Sigma }$.

Por cada palabra w en${\displaystyle \Sigma ^{*}}$, dejar${\displaystyle T_{w}\colon Q\to Q}$Sea la función, definida recursivamente, de la siguiente manera, para todo q en Q :

• Si${\displaystyle w=\varepsilon}$, entonces${\displaystyle T_{\varepsilon }(q)=q}$, de modo que la palabra vacía${\displaystyle \varepsilon }$no cambia el estado.
• Si${\displaystyle w=\sigma }$es una carta en${\displaystyle \Sigma }$, entonces${\displaystyle T_{\sigma }(q)=T(q,\sigma )}$.
• Si${\displaystyle w=\sigma v}$para${\displaystyle \sigma \in \Sigma }$y${\displaystyle v\en \Sigma ^{*}}$, entonces${\displaystyle T_{w}(q)=T_{v}(T_{\sigma }(q))}$.

Dejar${\displaystyle M(Q,\Sigma ,T)}$ser el conjunto

${\displaystyle M(Q,\Sigma ,T)=\{T_{w}\vert w\in \Sigma ^{*}\}.}$

El conjunto${\displaystyle M(Q,\Sigma ,T)}$es cerrado bajo composición de funciones ; es decir, para todo${\displaystyle v,w\in \Sigma ^{*}}$, uno tiene${\displaystyle T_{w}\circ T_{v}=T_{vw}}$También contiene${\ Displaystyle T _ {\ varepsilon}}$, que es la función identidad en Q . Dado que la composición de funciones es asociativa , el conjunto${\displaystyle M(Q,\Sigma ,T)}$es un monoide: se le llama monoide de entrada , monoide característico , semigrupo característico o monoide de transición del semiautómata.${\displaystyle (Q,\Sigma ,T)}$.

Si el conjunto de estados Q es finito, entonces las funciones de transición se representan comúnmente como tablas de transición de estados . La estructura de todas las transiciones posibles impulsadas por cadenas en el monoide libre tiene una representación gráfica como un grafo de De Bruijn .

El conjunto de estados Q no tiene por qué ser finito, ni siquiera numerable. Como ejemplo, los semiautómatas sustentan el concepto de autómatas cuánticos finitos . Allí, el conjunto de estados Q viene dado por el espacio proyectivo complejo.${\displaystyle \mathbb {C} P^{n}}$y los estados individuales se denominan cúbits de n estados . Las transiciones de estado se dan mediante matrices unitarias de n × n . El alfabeto de entrada${\displaystyle \Sigma }$sigue siendo finito, y otras preocupaciones típicas de la teoría de autómatas siguen vigentes. Por lo tanto, el semiautómata cuántico puede definirse simplemente como el triple${\displaystyle (\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}}\})}$cuando el alfabeto${\displaystyle \Sigma }$tiene p letras, de modo que hay una matriz unitaria${\displaystyle U_{\sigma }}$para cada letra${\displaystyle \sigma \in \Sigma }$Dicho de esta manera, el semiautómata cuántico tiene muchas generalizaciones geométricas. Así, por ejemplo, se puede tomar un espacio simétrico riemanniano en lugar de${\displaystyle \mathbb {C} P^{n}}$y selecciones de su grupo de isometrías como funciones de transición.

El monoide sintáctico de un lenguaje regular es isomorfo al monoide de transición del autómata mínimo que acepta dicho lenguaje.

• AH Clifford y GB Preston , La teoría algebraica de los semigrupos . American Mathematical Society, volumen 2 (1967), ISBN 978-0-8218-0272-4.
• F. Gecseg e I. Peak, Teoría algebraica de autómatas (1972), Akademiai Kiado, Budapest.
• WML Holcombe, Teoría de autómatas algebraicos (1982), Cambridge University Press
• JM Howie , Autómatas y lenguajes , (1991), Clarendon Press, ISBN 0-19-853442-6.
• Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoides, actos y categorías (2000), Walter de Gruyter, Berlín, ISBN 3-11-015248-7.
• Rudolf Lidl y Günter Pilz, Álgebra abstracta aplicada (1998), Springer, ISBN 978-0-387-98290-8