Autómata probabilístico

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 en la función de transición , convirtiéndola en una matriz de transición . ^{[ 1 ] [ 2 ]} Por lo tanto, 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 se conoce a veces como 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 .

Para un estado inicial y un carácter de entrada dados, un autómata finito determinista (AFD) tiene exactamente un estado siguiente, y un autómata finito no determinista (AFN) tiene un conjunto de estados siguientes. Un autómata probabilístico (AP), 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 se acepta si su probabilidad total de estar en un estado de aceptación supera un cierto umbral.

Un autómata finito (AF) representa, en cierto modo, un paso intermedio entre lo determinista y lo no determinista, ya que permite un conjunto de estados siguientes, pero con restricciones en sus ponderaciones. Sin embargo, esta definición puede resultar algo engañosa, puesto que el AF utiliza la noción de números reales para definir las ponderaciones, algo que no se encuentra en la definición de los autómatas finitos deterministas (AFD) ni de los autómatas finitos no deterministas (AFND). Esta libertad adicional les permite decidir lenguajes no regulares, como los lenguajes p-ádicos con parámetros irracionales. Por consiguiente, los AF son más potentes que los AFD y los AFND (que, como es sabido, son igualmente potentes).

El autómata probabilístico puede definirse como una extensión de un autómata finito no determinista.${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$, junto con dos probabilidades: la probabilidad${\displaystyle P}$de que se produzca una transición de estado particular, y con el estado inicial${\displaystyle q_{0}}$reemplazado por un vector estocástico que da la probabilidad de que el autómata esté en un estado inicial dado.

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${\displaystyle F}$distinguidos como estados de aceptación (o finales )${\displaystyle F\subseteq Q}$.

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

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

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

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

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

La matriz${\displaystyle \theta _{a}}$es entonces una matriz cuadrada, cuyas entradas son cero o uno, indicando si una transición${\displaystyle q{\stackrel {a}{\rightarrow }}q^{\prime }}$Está permitido por el autómata finito no determinista (AFN). Dicha matriz de transición 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.${\displaystyle P_{a}}$, para cada símbolo a del alfabeto${\displaystyle \Sigma }$de modo que la probabilidad de una transición viene dada por

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

Un cambio de estado de algún estado a cualquier otro 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${\displaystyle a}$y estados internos${\displaystyle q}$El estado inicial de un autómata probabilístico viene dado por un vector fila .${\displaystyle v}$, cuyos componentes son las probabilidades de los estados iniciales individuales${\displaystyle q}$, que suman 1:

${\displaystyle \sum _{q}\left[v\right]_{q}=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${\displaystyle abc}$, sería

${\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 también es un vector estocástico. Este vector se denomina a veces distribución de estados , haciendo hincapié en que se trata de 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 cual se puede prescindir. Formalmente, un autómata probabilístico PA se define como la tupla${\displaystyle (Q,\Sigma ,P,v,F)}$Un autómata de Rabin es aquel para el cual la distribución inicial es${\displaystyle v}$es un vector de coordenadas ; es decir, tiene cero para todas las entradas excepto una, y la entrada restante es uno.

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

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

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

dónde${\displaystyle \Sigma ^{*}}$es el conjunto de todas las cadenas del alfabeto${\displaystyle \Sigma }$(de modo que * es la estrella de Kleene ). El lenguaje depende del valor del punto de corte.${\displaystyle \eta }$, normalmente se considera que está en el rango${\displaystyle 0\leq \eta <1}$.

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

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

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

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

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

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

Todo lenguaje estocástico puede representarse mediante un autómata de Rabin.

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

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

${\displaystyle L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}<p{\text{ y }}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 , de tal manera que sean mayores que${\displaystyle \eta }$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${\displaystyle \eta }$es racional.

El autómata probabilístico tiene una interpretación geométrica: el vector de estado puede entenderse como un punto situado en la cara del simplex estándar , opuesto a la esquina ortogonal. Las matrices de transición forman un monoide que actúa sobre dicho punto. Esto puede generalizarse considerando que el punto pertenece a un espacio topológico general , mientras que las matrices de transición se eligen de un conjunto de operadores que actúan sobre dicho espacio, formando así un semiautómata . Cuando el punto de corte se generaliza adecuadamente, se obtiene un autómata topológico .

Un ejemplo de dicha 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 en el valor máximo del ángulo cuántico .

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