Automatas

Solo disponible en BuenasTareas
  • Páginas : 4 (902 palabras )
  • Descarga(s) : 0
  • Publicado : 17 de noviembre de 2013
Leer documento completo
Vista previa del texto
AUTÓMATAS PROBABILÍSTICOS O ESTOCÁSTICOS
En su funcionamiento interviene el concepto de probabilidad, asociada a que se produzca una
determinada transición. Son autómatas finitos en los que lastransiciones entre estados a
partir de símbolos de entrada pueden no producirse de forma segura (probabilidad = 1) sino
que existe una determinada probabilidad asociada a que se produzca la transición.No se
habla del estado en el que se encuentra el autómata en un determinado instante, sino de la
probabilidad de que se encuentre en cada uno de los estados del autómata. Aplicaciones
realesbasadas en comportamientos probabilísticos de transición, ej. Movimiento de robots,
reconocimiento de voz, lenguaje natural, etc.
Definición
AFP = (Σ, Q, M, P(0), F), es una quíntupla
Σ: alfabeto deentrada Q: conjunto de estados, finito y no vacío M: conjunto de matrices de
probabilidad de transición entre estados.
M = {Ma  a ∈ Σ}, Ma contiene las probabilidades de transición de un estado aotro cuando se
recibe el símbolo a. Para cada símbolo del alfabeto, existe una matriz de probabilidades
vector de estado inicial P (0): contiene la probabilidad de encontrarse en el estado inicial.Cada estado de Q tiene asociada una probabilidad de ser el estado inicial F⊆Q: Conjunto de
estados finales o de aceptación (no vacío).

Matrices de Probabilidad de Transición:
Por cada símbolo a deΣ se define una matriz de probabilidad de transición, M(a), que define la
probabilidad de dado que el autómata se encuentre en un determinado estado y reciba el
símbolo de entrada a, transite acada uno de los demás estados.
p11 p12 ... p1n
∀a ∈ Σ, ∃ M(a) =
p21 p22 ... P2n ... ...... .... pn1 pn2 ....pnn
donde: n: número de estados: Q pij: probabilidad de que estando en el estado i yrecibiendo
una a como entrada, transite al estado j. 0 ≤Pij ≤ 1 para cada estado i, se cumple: ∑ pij = 1
n j =1

Vectores de estados
P(t) es el vector de estados en un instante t. Indica la...
tracking img