Autômato Probabilístico

Em matemática e ciência da computação, o autômato probabilístico (AP) é uma generalização do autômato finito não determinístico; que inclui a probabilidade de uma dada transição para a função de transição, transformando-a numa matriz de transição ou matriz estocástica. Assim, o autômato probabilístico generaliza o conceito de uma Cadeia de Markov ou submudança de tipo infinito. As linguagens reconhecidas pelo autômato probabilístico são chamadas de linguagens estocásticas; que incluem as linguagens regulares como um subconjunto. O número de linguagens estocásticas é incontável.

O conceito foi introduzido por Michael O. Rabin em 1963; de um determinado caso especial também conhecido como o Autômato de Rabin. Nos últimos anos, a variante foi formulada em termos de probabilidades quânticas, o Autômato quântico.

Definição

O autômato probabilístico pode ser definido como uma extensão de um autômato finito não-determinístico $(Q,\Sigma ,\delta ,q_{0},F)$, em conjunto com duas probabilidades: a probabilidade $P$ de uma transição de estado ocorrer, e com o estado inicial $q_{0}$ substituído por um vetor estocástico dando a probabilidade de um autômato existir em um dado estado inicial.

Para o autômato finito não-determinístico comum, temos

• um finito conjunto de estados $Q$
• um conjunto finito de símbolos $\Sigma$
• uma função de transição $\delta :Q\times \Sigma \to P(Q)$
• um conjunto de estados $F$ definido como de aceitação (ou final) $F\subset Q$.

Aqui, $P(Q)$ indica o Conjunto de partes de $Q$.

com o uso de currying, a função de transição $\delta :Q\times \Sigma \to P(Q)$ de um autômato finito não determinístico pode ser escito como uma Função indicadora

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

de modo que $\delta (q,a,q^{\prime })=1$ se $q^{\prime }\in \delta (q,a)$ e $\delta (q,a,q^{\prime })=0$ se $q^{\prime }\notin \delta (q,a)$. A função de transição curry pode ser entendida para ser uma matriz de matrizes de entrada.

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

A matriz $\theta _{a}$ é então uma matriz quadrada, cujas entradas são zero ou um, indicando se a transição $q{\stackrel {a}{\rightarrow }}q^{\prime }$ é perminitida pelo AFN. Toda matriz de transição é sempre definida por um autômato finito não-determinístico.

O autômato probabilístico substitui essa matriz por um matiz estocástica $P$,de modo que a probabilidade de uma transição é dada por

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

A mudança de estado de um para outro deve ocorrer com uma probabilidade, claro, por isso deve-se ter

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

para todos os símbolos de entrada $a$ e estados internos $q$. O estado inicial de um autômato probabilístico é dado por um vetor linha $v$,cujos componentes adicionam à unidade:

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

A matriz de transição atua na direita, de modo que o estado do autômato probabilístico, depois de consumir a cadeia de entrada $abc$, seria

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

Em particular, o estado de um autômato probabilístico é sempre um vetor estocástico, já que o produto de quaisquer duas matrizes estocásticas é uma matriz estocástica, e o produto de um vetor estocástico e uma matriz estocástica é novamente um vetor estocástico. Este vetor às vezes é chamado de distribuição de estados, enfatizando que é umadistribuição de probabilidade.

Formalmente, a definição de um autômato probabilístico não requer uma mecânica de um autômato finito não-determinístico, que pode ser dispensado. Formalmente, um autômato probabilístico AP é definido como uma tupla $(Q,\Sigma ,P,v,F)$. Um Autômato de Rabin é aquele cuja distribuição inicial $v$ é um vetor de coordenadas; ou seja, tem zero para todas as entradas menos uma, sendo essa remanescente um.

Linguagens Estocásticas

O conjunto de linguagens reconhecidas por um autômato probabilístico são chamadas linguagens estocásticas. Elas incluem as linguagens regulares como um subconjunto.

Seja $F=Q_{\text{aceitação}}\subset Q$ o conjunto de estados de "aceitação" ou "finais" de um autômato. Por abuso de notação, $Q_{\text{aceitação}}$ pode ser também entendido para ser o vetor coluna que é o Conjunto de partes para $Q_{\text{aceitação}}$;isto é, que tem um 1 nos locais correspondentes aos elementos em $Q_{\text{aceitação}}$, e um zero nos outros. Este vetor pode ser contraído com a probabilidade do estado interno, para formar um escalar. A linguagem reconhecida por um autômato específico é definida como

$L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{aceitação}}>\eta \}$

onde $\Sigma ^{*}$ é o conjunto de todas cadeia no alfabeto $\Sigma$ (de modo que * é fecho de Kleene). A linguagem depende do valor do ponto de corte $\eta$, normalmente usado para ser o intervalo $0\leq \eta <1$.

Uma linguagem é chamada η-estocástica se e somente se existe algum AP que reconhece a linguagem, para um fixo $\eta$. Uma linguagem é dita estocástica se e somente se existe algum $0\leq \eta <1$ de modo que $L_{\eta }$ é η-estocástica.

Um ponto de corte é dito para ser um ponto de corte isolado se e apenas se existe existe um $\delta >0$ tal que

$\vert vP(s)Q_{\text{aceitação}}-\eta \vert \geq \delta$

para todo $s\in \Sigma ^{*}$

Propriedades

Toda linguagem regular é estocástica, e mais fortemente, cada linguagem regular é η-estocástica. Uma conversão fraca é que toda linguagem 0-estocástica é regular; no entanto, a conversão geral não se aplica: existem linguagens estocásticas que não são regulares.

Toda linguagem η-estocástica é estocástica, para algum $0<\eta <1$.

Toda linguagem estocástica é representável por um Autômato de Rabin.

Se $\eta$ é um caso de ponto de corte isolado, então $L_{\eta }$ é uma linguagem regular.

Linguagens p-ádicas

A linguagem p-ádica é um exemplo de um linguagem estocástica que não é regular, e também mostra que o número de linguagens estocásticas é incontável. A linguagem p-ádica é definida como um conjunto de cadeias com símbolos $0,1,2,\ldots ,(p-1)$ de modo que

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

Ou seja, uma linguagem p-ádica é apenas um conjunto de números reais, escrito na base de p, de modo que eles são superiores a $\eta$. É simples mostrar que toda as linguagens p-ádicas são estocásticas. No entanto, uma linguagem p-ádica é regular se e somente se $\eta$ é racional. Em particular, isto implica que o número de linguagens estocásticas é incontável.

Generalizações

O autômato probabilístico tem uma interpretação geométrica: o vetor de estados pode ser considerado como sendo um que vive na face da norma simplex (topologia), opostamente ao lado ortogonal. As matrizes de transição formam um monoide, agindo nesse ponto. Isto pode ser generalizado por ter o ponto a partir de algum espaço topológico genérico, enquanto matrizes de transição são escolhidas a partir de um conjunto de operadores que atuam sobre o espaço topológico, formando assim um semi-autômato. Quando o ponto de corte é adequadamente generalizado, existe um autômato quântico.

Um exemplo de tal generalização é o autômato quântico; aqui, o estado do autômato é representado por um ponto em um espaço projetivo complexo, enquanto que as matrizes de transição são um conjunto fixo escolhido a partir do grupo unitário. O ponto de corte é entendido como um limite para o valor máximo de um autômato quântico.

Referências

• Arto Salomaa, Theory of Automata (1969) Pergamon Press, Oxford (Ver capítulo 2).