semiautómata

En matemáticas e informática teórica , un semiautómata es un autómata finito determinista que tiene entradas pero no salida. Consiste en 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 Clifford y Preston (1967), las acciones de semigrupos se denominan "operandos".

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

Transformación de semigrupos y actos monoides.

Un semigrupo de transformación o monoide de transformación es un par que consta de un conjunto Q (a menudo llamado "conjunto de estados ") y un semigrupo o monoide M de funciones , o "transformaciones", que asignan Q a sí mismo. Son funciones en el sentido de que cada elemento m de M es un mapa . 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 "semigrupo" y "monoide" como sinónimos. Aquí un semigrupo no necesita tener un elemento de identidad ; un monoide es un semigrupo con un elemento de identidad (también llamado "unidad"). Dado que la noción de funciones que actúan sobre un conjunto siempre incluye la noción de una función de identidad, que cuando se aplica al conjunto no hace nada, un semigrupo de transformación se puede convertir en un monoide agregando la función de identidad.

M -actos

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 correcto o simplemente acto correcto . En pocas palabras, es la multiplicación correcta de elementos de Q por elementos de M. El acto correcto a menudo se escribe 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}$

Un acto M está estrechamente relacionado con un monoide de transformación. Sin embargo, los elementos de M no tienen por qué 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 algunos arbitrarios , como ocurre con la composición de funciones. ${\displaystyle \mu }$ ${\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}$ ${\displaystyle \mu }$

Una vez que uno hace esta demanda, es completamente seguro eliminar todos los paréntesis, ya que el producto monoide y la acción del monoide en el conjunto son completamente asociativos . En particular, esto permite representar los elementos del monoide como cadenas de letras, en el sentido informático de la palabra "cadena". Esta abstracción permite entonces hablar de operaciones con cadenas en general y, finalmente, conduce al concepto de que los lenguajes formales están compuestos por 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 acto M es esencialmente lo mismo que un monoide de transformación.

M -homomorfismo

Para dos M -actos y compartiendo el mismo monoide , un M -homomorfismo es un mapa 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 homomorfismos M 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 .

semiautómata

Un semiautómata es un triple 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 tiene por qué serlo), se puede pensar en un semiautómata 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 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 de . ${\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 , entonces . ${\displaystyle w=\sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle T_{\sigma }(q)=T(q,\sigma )}$
• Si por 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 composición de funciones ; es decir, para todos , uno tiene . También contiene , que es la función identidad en Q . Dado que la composición de funciones es asociativa , el conjunto es un monoide: se llama 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, 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 cuerdas en el monoide libre tiene una representación gráfica como un gráfico de De Bruijn .

El conjunto de estados Q no tiene por qué ser finito, ni siquiera contable. Por 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 , 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 los autómatas siguen en juego. Así, 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 . Dicho de esta manera, el semiautómata cuántico tiene muchas generalizaciones geométricas. Así, por ejemplo, se 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.

Referencias

• AH Clifford y GB Preston , La teoría algebraica de los semigrupos . Sociedad Estadounidense de Matemáticas, volumen 2 (1967), ISBN  978-0-8218-0272-4 .
• F. Gecseg e I. Peak, Teoría algebraica de los autómatas (1972), Akademiai Kiado, Budapest.
• WML Holcombe, Teoría de los 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