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)*)))

  q 2 = 1*q 2 + 0*q 2 q 1 =1*q 1 + 0(1*q 2 + 0*q 2 ) Solución :  q 0 =0*q 0 + 1(1*q 1 + 0(1*q 2 + 0*q 2 ))

 

 1.Analizar el grafo. 2.Representar los estados con ecuaciones 3.Tomar en cuenta las transiciones  para concatenar los posibles resultados 4 .En el estado de aceptación se le pondrá Lambda que representa  el estado vacío 5.La estrella de Kleene se pone cuando se esta repitiendo a si mismo 6.Ya que las ecuaciones están listas se resuelve de abajo hacia arriba q_0=1q_0 + 0_q1(Lamda) q_1=1q_1 (Lamda)+ 0q_0 q_0=1* + 0q_1 q_1=1*+0q_0 q_1=1*+ 0q_0 q_0=1*+(1*+0q_0)

Expresión Regular: Es una descripción compacta y fácil de leer de un lenguaje regular   1. SINÓNIMO DE AUTÓMATA FINITO R=Máquina De Estado Finito 2. ES EL ESTADO FINAL R=Aceptación  3. PUNTOS DONDE SE DESPLAZARA EL AUTOMATA R= Transición  4. FINALIDAD DEL AF AL RECONOCER LENGUAJES DE ESTE TIPO R=Regulares 5. LOS LENGUAJES REGULARES PERTENECEN A ESTOS LENGUAJES FORMALES R=Formales 6. SE REPRESENTA CON LA LETRA SIGMA R=Alfabeto 7.  ES EL PRIMER ESTADO R=Inicial 8. PUNTOS DONDE SE DESPLAZARA EL AUTOMATA R=Estado 9. REPRESENTACION SIMBOLICA DE UN ESTADO FINITO R=Grafo  

Los compiladores son programas de computadora que traducen de un lenguaje a otro. Un compilador toma como su entrada un programa escrito en lenguaje fuente y produce un programa equivalente escrito en lenguaje objeto. Un compilador se compone internamente de varias etapas, o fases, que realizan operaciones lógicas.   1.-Analizador léxico:                                                                                                                                Lee la secuencia de caracteres de izquierda a derecha del programa fuente y agrupa las secuencias de caracteres en unidades con significado propio (componentes léxicos o “tokens” en ingles).  Las palabra...

DEFINICIÓN:                                                                                                                                                                     Un traductor es un programa que tiene como entrada un texto escrito en un lenguaje (lenguaje fuente) y como salida produce un texto escrito en un lenguaje (lenguaje objeto) que preserva el significado de origen. INTERPRETES:  Los interpretes son los que realizan normalmente dos operaciones: Traducen el código fuente a un formato interno. Ejecuta o interpretan el programa traducido al formato interno. D...

LENGUAJES: Es un conjunto de cadenas, de todas las seleccionadas de un Σ*. donde Σ determinado el alfabeto se denomina lenguaje. Si Σ es un alfabeto y L Σ*, entonces L es un lenguaje de Σ. Observe que un lenguaje de Σ no necesita incluir cadenas con todos los símbolos de Σ, ya que una vez que hemos esta que L es un lenguaje de Σ, también sabemos que es un lenguaje de cualquier alfabeto que sea un súper conjunto de Σ. La elección del termino "lenguaje" puede parecer extraña. Sin embargo, los lenguajes habituales pueden interpretarse como conjuntos de cadenas. Un ejemplo seria el Ingles, donde la colección de las palabras correctas inglesas es un conjunto de cadenas del alfabeto que consta de todas las letras. Otro ejemplo es el lenguaje C.   Tipos de lenguajes: LENGUAJE NATURAL:  Nosotros estamos relacionados con el concepto tradicional de gramática que, de esta forma intuitiva, podemos considerar un conjunto de reglas el cual nos indican que es correcto y que no lo es del...

  A grandes rasgos, un compilador es un programa que lee un programa escrito en un lenguaje, el lenguaje fuente, y lo traduce a un programa equivalente en otro lenguaje, el lenguaje objeto. como parte importante de este proceso de traducción, el compilador informa a su usuario de la presencia de errores en el programa fuente. A primera vista, la diversidad de los compiladores puede parecer abrumadora. Hay miles de lenguajes fuente, desde los lenguajes de programación tradicionales, como FORTRAN o Pascal, hasta los lenguajes especializados que han surgido virtualmente en todas las áreas de aplicación de la informática. Los lenguajes objeto son igualmente variados; un lenguaje objeto puede ser otro lenguaje de programación.