Lenguajes y Autómatas 1

Expresión regular  x y z* + y x z* GRAFO

 ¿Qué es? Un autómata finito “no determinista” (AFN) tiene la capacidad de estar en varios estados a la vez. Esta capacidad a menudo se expresa como la posibilidad de que el autómata “conjeture” algo acerca de su entrada. Una transición puede llevar a múltiples estados. Construcción Un AFN se representa esencialmente como un AFD:  A = (Q,Σ,δ,q0,F)  donde:  1. Q es un conjunto finito de estados.  2. Σ es un conjunto finito de símbolos de entrada.  3. q0, un elemento de Q, es el estado inicial.  4. F, un subconjunto de Q, es el conjunto de estados finales (o de aceptación).  5. δ, la función de transición, es una función que toma como argumentos un estado de Q y un símbolo de entrada de Σ y devuelve un subconjunto de Q. Observe que la única diferencia entre un AFN y un AFD se encuentra en el tipo de valor que devuelve δ: un conjunto de estados en el caso de un AFN y un único estado en el caso de un AFD.  Lenguaje Un AFN acepta una cadena w si e...

¿Qué es? Es aquel que sólo puede estar en un único estado después de leer cualquier secuencia de entradas. El término “determinista” hace referencia al hecho de que para cada entrada sólo existe uno y sólo un estado al que el autómata puede hacer la transición a partir de su estado actual. La transición solo puede llevar a un estado ya definido Construcción Un autómata finito determinista consta de:  1. Un conjunto finito de estados, a menudo designado como Q.  2. Un conjunto finito de símbolos de entrada, a menudo designado como Σ.  3. Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designa habitualmente como δ. En nuestra representación gráfica informal del autómata, δ se ha representa mediante arcos entre los estados y las etiquetas sobre los arcos. Si q es un estado y a es un símbolo de entrada, entonces δ(q,a) es el estado p tal que existe un arco etiquetado a que va desde q hasta ...

Expresión Regulas. a* b a + a b a* Autómata.  

Autómata  finito. es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida. La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky. Definición formal Formalmente: E: alfabeto de entrada. Q: conjunto de estados; es conjunto finito no vacío. f: función de transición. f(p, a)=q q0 : (perteneciente a Q) estado inicial. F : (perteneciente a Q) conjunto de estados finales o de ac...

  q 3 =a* q 2 =mq1 q 1 =h(a*) + a(m(q1))   Solución: q 0 =m[h(a* + a(m(q 1 ))) + h(m(h(a*) +(m(q 1 ))))]

q 4 =b*+ a(cq 4 ) q 3 =c(b* + aq 3 ) q 2 =c* + b(c(b* + a)*) q 1 =b(b* + (b+ a) (c(b*+ a)*))  Solución: q 0 =a(b(c* + (b + a) (c(b* + a)*)))