En matemáticas e informática , el autómata probabilístico ( AP ) es una generalización del autómata finito no determinista ; incluye la probabilidad de una transición dada a la función de transición , convirtiéndola en una matriz de transición . Así, el autómata probabilístico también generaliza los conceptos de cadena de Markov y de subdesplazamiento de tipo finito . Los lenguajes reconocidos por los autómatas probabilísticos se denominan lenguajes estocásticos ; estos incluyen los idiomas regularescomo un subconjunto. El número de lenguajes estocásticos es incontable .
El concepto fue introducido por Michael O. Rabin en 1963; [1] Cierto caso especial se conoce a veces como el autómata de Rabin (que no debe confundirse con la subclase de ω-autómatas también denominados autómatas de Rabin). En los últimos años, se ha formulado una variante en términos de probabilidades cuánticas, el autómata finito cuántico .
Definición
El autómata probabilístico puede definirse como una extensión de un autómata finito no determinista , junto con dos probabilidades: la probabilidad de una transición de estado particular que está teniendo lugar, y con el estado inicial reemplazado por un vector estocástico que da la probabilidad de que el autómata se encuentre en un estado inicial dado.
Para el autómata finito no determinista ordinario, uno tiene
- un conjunto finito de estados
- un conjunto finito de símbolos de entrada
- una función de transición
- un conjunto de estados distinguidos como estados de aceptación (o finales ) .
Aquí, denota el conjunto de poder de.
Mediante el uso de curry , la función de transiciónde un autómata finito no determinista se puede escribir como una función de pertenencia
así que eso Si y Si . La función de transición al curry puede entenderse como una matriz con entradas de matriz.
La matriz es entonces una matriz cuadrada, cuyas entradas son cero o uno, lo que indica si una transición está permitido por la NFA. Una matriz de transición de este tipo siempre se define para un autómata finito no determinista.
El autómata probabilístico reemplaza estas matrices por una familia de matrices estocásticas derechas , para cada símbolo a en el alfabeto de modo que la probabilidad de una transición viene dada por
Un cambio de estado de algún estado a cualquier estado debe ocurrir con probabilidad uno, por supuesto, y así uno debe tener
para todas las letras de entrada y estados internos . El estado inicial de un autómata probabilístico está dado por un vector fila , cuyos componentes son las probabilidades de los estados iniciales individuales , que se suman a 1:
La matriz de transición actúa a la derecha, de modo que el estado del autómata probabilístico, después de consumir la cadena de entrada , sería
En particular, el estado de un autómata probabilístico es siempre un vector estocástico, ya que el producto de dos matrices estocásticas cualesquiera es una matriz estocástica, y el producto de un vector estocástico y una matriz estocástica es nuevamente un vector estocástico. Este vector a veces se denomina distribución de estados , enfatizando que es una distribución de probabilidad discreta .
Formalmente, la definición de un autómata probabilístico no requiere la mecánica del autómata no determinista, de la que se puede prescindir. Formalmente, un autómata probabilístico PA se define como la tupla. Un autómata Rabin es aquel para el que la distribución iniciales un vector de coordenadas ; es decir, tiene cero para todas las entradas menos una y la entrada restante es una.
Lenguas estocásticas
El conjunto de lenguajes reconocidos por los autómatas probabilísticos se denominan lenguajes estocásticos . Incluyen los idiomas regulares como un subconjunto.
Dejar ser el conjunto de estados "aceptables" o "finales" del autómata. Por abuso de notación,también puede entenderse como el vector de columna que es la función de pertenencia para; es decir, tiene un 1 en los lugares correspondientes a los elementos eny un cero en caso contrario. Este vector puede contraerse con la probabilidad de estado interno, para formar un escalar . El lenguaje reconocido por un autómata específico se define entonces como
dónde es el conjunto de todas las cadenas del alfabeto (de modo que * es la estrella de Kleene ). El idioma depende del valor del punto de corte. , normalmente se considera que está en el rango .
Un idioma se llama η- estocástico si y solo si existe algún PA que reconoce el idioma, por. Un lenguaje se llama estocástico si y solo si hay alguna para cual es η- estocástico.
Se dice que un punto de corte es un punto de corte aislado si y solo si existe un tal que
para todos
Propiedades
Cada idioma regular es estocástico y, más fuertemente, cada idioma regular es η -estocástico. Un inverso débil es que todo lenguaje estocástico 0 es regular; sin embargo, lo contrario general no es válido: hay lenguajes estocásticos que no son regulares.
Todo lenguaje η -estocástico es estocástico, para algunos.
Todo lenguaje estocástico es representable por un autómata de Rabin.
Si es un punto de corte aislado, entonces es un idioma regular.
p -lenguas ádicas
Los lenguajes p -ádicos proporcionan un ejemplo de un lenguaje estocástico que no es regular, y también muestran que el número de lenguajes estocásticos es incontable. Un lenguaje p -ádico se define como el conjunto de cadenas
en las letras .
Es decir, un lenguaje p -ádico es simplemente el conjunto de números reales en [0, 1], escritos en base- p , de modo que son mayores que. Es sencillo demostrar que todos los lenguajes p -ádicos son estocásticos. En particular, esto implica que el número de lenguajes estocásticos es incontable. Un lenguaje p -ádico es regular si y solo si es racional.
Generalizaciones
El autómata probabilístico tiene una interpretación geométrica: el vector de estado puede entenderse como un punto que vive en la cara del símplex estándar , opuesto a la esquina ortogonal. Las matrices de transición forman un monoide que actúa sobre el punto. Esto puede generalizarse haciendo que el punto sea de algún espacio topológico general , mientras que las matrices de transición se eligen de una colección de operadores que actúan sobre el espacio topológico, formando así un semiautomatón . Cuando el punto de corte está adecuadamente generalizado, se tiene un autómata topológico .
Un ejemplo de tal generalización es el autómata finito cuántico ; aquí, el estado del autómata está representado por un punto en el espacio proyectivo complejo , mientras que las matrices de transición son un conjunto fijo elegido del grupo unitario . El punto de corte se entiende como un límite del valor máximo del ángulo cuántico .
Notas
- ^ Michael O. Rabin (1963). "Autómatas probabilísticos" . Información y control . 6 (3): 230–245. doi : 10.1016 / s0019-9958 (63) 90290-0 .
Referencias
- Salomaa, Arto (1969). "Autómatas probabilísticos y no deterministas finitos". Teoría de los autómatas . Oxford: Pergamon Press .