Autómata probabilístico

En matemáticas e informática , el autómata probabilístico ( PA ) es una generalización del autómata finito no determinista ; incluye la probabilidad de una transición dada en la función de transición , convirtiéndola en una matriz de transición . ^{[1] [2]} 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 lenguajes regulares como un subconjunto. El número de lenguajes estocásticos es incontable .

El concepto fue introducido por Michael O. Rabin en 1963; ^[2] un caso especial a veces se conoce como el autómata de Rabin (que no debe confundirse con la subclase de ω-autómatas también conocidos como 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 .

Descripción informal

Para un estado inicial y un carácter de entrada dados, un autómata finito determinista (DFA) tiene exactamente un estado siguiente, y un autómata finito no determinista (NFA) tiene un conjunto de estados siguientes. Un autómata probabilístico (PA) en cambio tiene un conjunto ponderado (o vector ) de estados siguientes, donde los pesos deben sumar 1 y por lo tanto pueden interpretarse como probabilidades (lo que lo convierte en un vector estocástico ). Las nociones de estados y aceptación también deben modificarse para reflejar la introducción de estos pesos. El estado de la máquina como un paso dado ahora también debe representarse mediante un vector estocástico de estados, y un estado aceptado si su probabilidad total de estar en un estado de aceptación excede algún límite.

Un PA es en cierto sentido un paso intermedio entre lo determinista y lo no determinista, ya que permite un conjunto de estados siguientes pero con restricciones en sus pesos. Sin embargo, esto es algo engañoso, ya que el PA utiliza la noción de números reales para definir los pesos, que está ausente en la definición tanto de los DFA como de los NFA. Esta libertad adicional les permite decidir lenguajes que no son regulares, como los lenguajes p-ádicos con parámetros irracionales. Como tal, los PA son más poderosos que los DFA y los NFA (que son famosamente igualmente poderosos).

Definición formal

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 que tenga lugar una transición de estado particular y con el estado inicial reemplazado por un vector estocástico que da la probabilidad de que el autómata esté en un estado inicial dado. ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$ ${\displaystyle P}$ ${\displaystyle q_{0}}$

Para el autómata finito no determinista ordinario, se tiene

• un conjunto finito de estados ${\displaystyle Q}$
• un conjunto finito de símbolos de entrada ${\displaystyle \Sigma }$
• una función de transición ${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$
• un conjunto de estados que se distinguen como estados de aceptación (o finales ) . ${\displaystyle F}$ ${\displaystyle F\subseteq Q}$

Aquí, denota el conjunto potencia de . ${\displaystyle \wp (Q)}$ ${\displaystyle Q}$

Mediante el uso de currificación , la función de transición de un autómata finito no determinista se puede escribir como una función de pertenencia. ${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$

${\displaystyle \delta :Q\times \Sigma \times Q\to \{0,1\}}$

De modo que si y en caso contrario. La función de transición currificada puede entenderse como una matriz con entradas de matriz. ${\displaystyle \delta (q,a,q^{\prime })=1}$ ${\displaystyle q^{\prime }\in \delta (q,a)}$ ${\displaystyle 0}$

${\displaystyle \left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q^{\prime })}$

La matriz es entonces una matriz cuadrada, cuyos valores son cero o uno, lo que indica si el NFA permite una transición. Una matriz de transición de este tipo siempre se define para un autómata finito no determinista. ${\displaystyle \theta _{a}}$ ${\displaystyle q{\stackrel {a}{\rightarrow }}q^{\prime }}$

El autómata probabilístico reemplaza estas matrices por una familia de matrices estocásticas rectas , para cada símbolo a en el alfabeto, de modo que la probabilidad de una transición está dada por ${\displaystyle P_{a}}$ ${\displaystyle \Sigma }$

${\displaystyle \left[P_{a}\right]_{qq^{\prime }}}$

Un cambio de estado de algún estado a cualquier estado debe ocurrir con probabilidad uno, por supuesto, y por lo tanto uno debe tener

${\displaystyle \sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1}$

para todas las letras de entrada y estados internos . El estado inicial de un autómata probabilístico está dado por un vector de fila , cuyos componentes son las probabilidades de los estados iniciales individuales , que suman 1: ${\displaystyle a}$ ${\displaystyle q}$ ${\displaystyle v}$ ${\displaystyle q}$

${\displaystyle \sum _{q}\left[v\right]_{q}=1}$

La matriz de transición actúa sobre la derecha, de modo que el estado del autómata probabilístico, después de consumir la cadena de entrada , sería ${\displaystyle abc}$

${\displaystyle vP_{a}P_{b}P_{c}}$

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 a su vez 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 de Rabin es aquel cuya distribución inicial es un vector de coordenadas ; es decir, tiene cero para todas las entradas excepto una, y la entrada restante es una. ${\displaystyle (Q,\Sigma ,P,v,F)}$ ${\displaystyle v}$

Lenguajes estocásticos

El conjunto de lenguajes reconocidos por los autómatas probabilísticos se denomina lenguajes estocásticos . Incluyen a los lenguajes regulares como un subconjunto.

Sea el conjunto de estados "aceptantes" o "finales" del autómata. Por abuso de notación, también puede entenderse como el vector columna que es la función de pertenencia para ; es decir, tiene un 1 en los lugares correspondientes a elementos en , y un cero en los demás. Este vector puede contraerse con la probabilidad de estado interna, para formar un escalar . El lenguaje reconocido por un autómata específico se define entonces como ${\displaystyle F=Q_{\text{accept}}\subseteq Q}$ ${\displaystyle Q_{\text{accept}}}$ ${\displaystyle Q_{\text{accept}}}$ ${\displaystyle Q_{\text{accept}}}$

${\displaystyle L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}>\eta \}}$

donde 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 , que normalmente se considera dentro del rango . ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \eta }$ ${\displaystyle 0\leq \eta <1}$

Un lenguaje se llama η -estocástico si y solo si existe algún PA que reconoce el lenguaje, para fijo . Un lenguaje se llama estocástico si y solo si existe algún para el cual es η -estocástico. ${\displaystyle \eta }$ ${\displaystyle 0\leq \eta <1}$ ${\displaystyle L_{\eta }}$

Se dice que un punto de corte es un punto de corte aislado si y sólo si existe un tal que ${\displaystyle \delta >0}$

${\displaystyle \vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta }$

a pesar de ${\displaystyle s\in \Sigma ^{*}}$

Propiedades

Todo lenguaje regular es estocástico y, más fuertemente, todo lenguaje regular es η -estocástico. Una recíproca débil es que todo lenguaje 0-estocástico es regular; sin embargo, la recíproca general no se cumple: hay lenguajes estocásticos que no son regulares.

Todo lenguaje η -estocástico es estocástico, para algún tipo de ... ${\displaystyle 0<\eta <1}$

Todo lenguaje estocástico es representable mediante un autómata de Rabin.

Si es un punto de corte aislado, entonces es un lenguaje regular. ${\displaystyle \eta }$ ${\displaystyle L_{\eta }}$

pag-lenguas ádicas

Los lenguajes p -ádicos proporcionan un ejemplo de un lenguaje estocástico que no es regular, y también muestran que la cantidad de lenguajes estocásticos es incontable. Un lenguaje p -ádico se define como el conjunto de cadenas

${\displaystyle L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ and }}0.n_{1}n_{2}n_{3}\ldots >\eta \}}$

en las cartas . ${\displaystyle 0,1,2,\ldots ,(p-1)}$

Es decir, un lenguaje p -ádico es simplemente el conjunto de números reales en [0, 1], escritos en base p , tales que son mayores que . Es sencillo demostrar que todos los lenguajes p -ádicos son estocásticos. ^[3] 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. ${\displaystyle \eta }$ ${\displaystyle \eta }$

Generalizaciones

El autómata probabilístico tiene una interpretación geométrica: el vector de estado puede entenderse como un punto que se encuentra 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 se puede generalizar 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 semiautómata . Cuando el punto de corte se generaliza adecuadamente, se tiene un autómata topológico .

Un ejemplo de esta generalización es el autómata finito cuántico ; en este caso, 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

1. Paz, Azaria (2014). Introducción a los autómatas probabilísticos. ISBN 9781483244655.OCLC 1027002902  .
2. Michael O. Rabin (1963). "Autómatas probabilísticos". Información y control . 6 (3): 230–245. doi : 10.1016/s0019-9958(63)90290-0 .
3. Merve Nur Cakir; Saleemi, Mehwish; Zimmermann, Karl-Heinz (2021). "Sobre la teoría de los autómatas estocásticos". arXiv : 2103.14423 [cs.FL].

Referencias

• Salomaa, Arto (1969). "Autómatas finitos no deterministas y probabilísticos". Teoría de los autómatas . Oxford: Pergamon Press .