Semiautomático

En matemáticas y en informática teórica , un semiautómata es un autómata finito determinista que tiene entradas pero no salidas. 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.

Asociado a cualquier semiautómata hay 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 inducida de Q.

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

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

Semigrupos de transformación y actos monoides

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

Algunos autores consideran que "semigrupo" y "monoide" son sinónimos. En este caso, un semigrupo no necesita tener un elemento identidad ; un monoide es un semigrupo con un elemento identidad (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, que cuando se aplica al conjunto no hace nada, un semigrupo de transformación puede convertirse en un monoide añadiendo la función identidad.

METRO-hechos

Sea M un monoide y Q un conjunto no vacío. Si existe una operación multiplicativa

${\displaystyle \mu \colon Q\times M\to Q}$

${\displaystyle (q,m)\mapsto qm=\mu (q,m)}$

que satisface las propiedades

${\displaystyle q1=q}$

para 1 la unidad del monoide, y

${\displaystyle q(st)=(qs)t}$

para todos y , entonces el triple se llama acto M recto o simplemente acto recto . En lenguaje sencillo, es la multiplicación recta de elementos de Q por elementos de M . El acto recto se escribe a menudo como . ${\displaystyle q\in Q}$ ${\displaystyle s,t\in M}$ ${\displaystyle (Q,M,\mu )}$ ${\displaystyle \mu }$ ${\displaystyle Q_{M}}$

Un acto de izquierda se define de manera similar, con

${\displaystyle \mu \colon M\times Q\to Q}$

${\displaystyle (m,q)\mapsto mq=\mu (m,q)}$

y a menudo se denota como . ${\displaystyle \,_{M}Q}$

Una M -act está estrechamente relacionada con un monoide de transformación. Sin embargo, los elementos de M no necesitan ser funciones per se , son solo elementos de algún monoide. Por lo tanto, se debe exigir que la acción de sea consistente con la multiplicación en el monoide ( es decir, ), ya que, en general, esto podría no ser válido para algún , de la misma manera que ocurre con la composición de funciones. ${\displaystyle \mu }$ ${\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}$ ${\displaystyle \mu }$

Una vez que se hace esta demanda, es completamente seguro eliminar todos los paréntesis, ya que el producto monoide y la acción del monoide sobre el conjunto son completamente asociativos . En particular, esto permite que los elementos del monoide se representen como cadenas de letras, en el sentido informático de la palabra "cadena". Esta abstracción permite entonces hablar sobre operaciones con cadenas en general y, finalmente, conduce al concepto de lenguajes formales compuestos de cadenas de letras. ^{[ se necesita más explicación ]}

Otra diferencia entre un M -act y un monoide de transformación es que, para un M -act Q , dos elementos distintos del monoide pueden determinar la misma transformación de Q. Si exigimos que esto no suceda, entonces un M -act es esencialmente lo mismo que un monoide de transformación.

METRO-homomorfismo

Para dos M -actos y compartiendo el mismo monoide , un M -homomorfismo es una función tal que ${\displaystyle Q_{M}}$ ${\displaystyle B_{M}}$ ${\displaystyle M}$ ${\displaystyle f\colon Q_{M}\to B_{M}}$ ${\displaystyle f\colon Q\to B}$

${\displaystyle f(qm)=f(q)m}$

para todos y . El conjunto de todos los M -homomorfismos se escribe comúnmente como o . ${\displaystyle q\in Q_{M}}$ ${\displaystyle m\in M}$ ${\displaystyle \mathrm {Hom} (Q_{M},B_{M})}$ ${\displaystyle \mathrm {Hom} _{M}(Q,B)}$

Los M -actos y M -homomorfismos juntos forman una categoría llamada M -Act . ^[1]

Semiautomáticos

Un semiautómata es una tripleta donde 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 (Q,\Sigma ,T)}$ ${\displaystyle \Sigma }$

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

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

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

Sea el monoide libre generado por el alfabeto (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 ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

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

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

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

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

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

Propiedades

Si el conjunto de estados Q es finito, 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 cuerdas en el monoide libre tiene una representación gráfica como un grafo de De Bruijn .

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

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

Literatura

• AH Clifford y GB Preston , La teoría algebraica de 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 

Referencias

1. Moghbeli-Damaneh, Halimeh (julio de 2020). "La categoría cerrada monoidal simétrica de conjuntos M cpo" (PDF) . Categorías y estructuras algebraicas generales con aplicaciones . 13 (1).