Semiautomatón
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 .
Un semigrupo de transformación o monoide de transformación es un par que consta de 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 la función .
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.
para todos y , entonces el triple se llama un acto M correcto o simplemente un acto correcto . En términos generales, es la multiplicación correcta de elementos de Q por elementos de M. El acto correcto a menudo se escribe como .
ya menudo se denota como .
