En matemáticas e informática teórica , un semiautomatón 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 con cualquier semiautomaton es un monoid llama el monoid característica , monoid de entrada , monoid transición o sistema de transición de la semiautomaton, que actúa sobre el conjunto de estados Q . Esto puede ser visto ya sea como una acción del monoide libre de cadenas en el alfabeto de entrada Σ, o como la inducida semigrupo de la transformación de Q .
En libros más antiguos como Clifford y Preston (1967) los actos S se denominan "operandos".
Semigrupos de transformación y actos monoides.
Un semigrupo de transformación o monoide de transformación es un parque consiste en un conjunto Q (a menudo llamado el "conjunto de estados ") y un semigrupo o monoide M de funciones , o "transformaciones", mapeando 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 de la semigrupo transformación, su producto semigrupo se define como su composición de funciones .
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 función identidad, que cuando se aplica al conjunto no hace nada, se puede convertir un semigrupo de transformación en un monoide agregando la función identidad.
M -actos
Sea M un monoide y Q un conjunto no vacío. Si existe una operación multiplicativa
que satisface las propiedades
para 1 la unidad del monoide, y
para todos y , luego el triple se llama un derecho M -act o simplemente un acto correcto . En mano larga,es la multiplicación correcta de elementos de Q por elementos de M . El acto correcto a menudo se escribe como.
Un acto de izquierda se define de manera similar, con
y a menudo se denota como .
Un acto M está estrechamente relacionado 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 tanto, hay que exigir que la acción deser consistente con la multiplicación en el monoide ( es decir ), ya que, en general, esto podría no ser válido para algunos , de la misma forma que lo hace con la composición de funciones.
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 en 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 de cadenas en general, y eventualmente conduce al concepto de lenguajes formales como compuestos de cadenas de letras. [ se necesita más explicación ]
Otra diferencia entre un M -act y una monoid transformación es que para un M -act Q , dos elementos distintos de la monoid 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
Por dos actos M y compartiendo el mismo monoide , un M -homomorfismo es un mapa tal que
para todos y . El conjunto de todos los homomorfismos M se escribe comúnmente como o .
Los M -actos y M -homomorfismos juntos forman una categoría llamada M -Acto .
Semiautomas
Un semiautomatón es un triple dónde 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
Cuando el conjunto de estados Q es un conjunto finito —no es necesario que lo sea—, se puede pensar en un semiautomatón como un autómata finito determinista , pero sin el estado inicial o conjunto de aceptar estados A . Alternativamente, es una máquina de estados finitos que no tiene salida y solo una entrada.
Cualquier semiautomatón induce un acto de un monoide de la siguiente manera.
Dejar ser el monoide libre generado por el alfabeto (de modo que se entiende que el superíndice * es la estrella de Kleene ); es el conjunto de todas las cadenas de longitud finita compuestas por las letras en.
Por cada palabra w en, dejar ser la función, definida recursivamente, como sigue, para todo q en Q :
- Si , luego , para que la palabra vacía no cambia el estado.
- Si es una carta en , luego .
- Si por y , luego .
Dejar ser el set
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 conjuntoes un monoide: se llama monoide de entrada , monoide característico , semigrupo característico o monoide de transición del semiautomatón.
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 posibles transiciones impulsadas por cadenas en el monoide libre tiene una representación gráfica como un gráfico de De Bruijn .
El conjunto de estados Q no necesita ser finito, ni siquiera contable. Como ejemplo, los semiautomas sustentan el concepto de autómatas finitos cuánticos . Allí, el conjunto de estados Q viene dado por el complejo espacio proyectivo , y los estados individuales se denominan qubits de n estados . Las transiciones de estado vienen dadas por matrices unitarias n × n . El alfabeto de entradasigue siendo finito, y otras preocupaciones típicas de la teoría de los autómatas siguen en juego. Por lo tanto, el semiautomatón cuántico puede definirse simplemente como el triple cuando el alfabeto tiene p letras, de modo que hay una matriz unitaria por cada letra . Dicho de esta manera, el semiautomatón cuántico tiene muchas generalizaciones geométricas. Así, por ejemplo, se puede tomar un espacio simétrico de Riemann en lugar dey 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 el lenguaje.
Referencias
- AH Clifford y GB Preston , The Algebraic Theory of Semigroups . Sociedad Americana 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 , Automata and Languages , (1991), Clarendon Press, ISBN 0-19-853442-6 .
- Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, Monoids, Acts and Categories (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