Lenguajes y Autómatas 1

  xyz* + yxz*

Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino, es decir, es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado, tal que para un símbolo   del alfabeto, existe más de una transición   posible. La definición formal de AFND se basa en la consideración de que a menudo según los algoritmos de transformación de expresiones y gramáticas regulares a AF terminan obteniéndose autómatas con transiciones múltiples para un mismo símbolo o transiciones vacías. Independientemente que sean indeseables, sobre todo para la implementación material, fundamentalmente mecánica, de los autómatas finitos, son imprescindibles durante la modelación de analizadores lexicográficos de los elementos gramaticales de los lenguajes de programación, llamados tókens, como literales numéricos, identificadores, cadenas de texto, operadores, etc. 1. Q es un conjunto finito de estados . 2...

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 puedykttke hacer la transición a partir de su estado actual. La transición desde un estado puede tener como destino un único estado. Por eso se llama determinista. No se aceptan transiciones con cadenas vacías. Se permite el uso de backtracking Requiere mas espacio. Una cadena es aceptada si su transición es hacia un estado final. Diagramas de transiciones Un diagrama de transiciones de un AFD A = (Q,Σ,δ,q0,F) es un grafo definido como sigue: a) Para cada estado de Q, existe un nodo. b) Para cada estado q de Q y cada símbolo de entrada a de Σ, sea δ(q,a) = p. Entonces, el diagrama de transiciones tiene un arco desde el nodo q hasta el nodo p, etiquetado como a. Si existen varios símbolos de entrada que dan lugar a transiciones desde q hasta p, entonces el ...

 

Un autómata finito (AF) o máquina de estado 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) conjunt...

Ejercicio  1 q0 = 0q0+1q1 q1 = 1q1+0q1λ q2 = 1q2λ+0q2λ q0 = 0*+1q1 q1 = 1*+0qλ q2 = 1*+0   Solución: q2 = 1*+0* q1 = 1*+0(1*+0*) q = 0*+1(1*+0(1*+0*)) Ejercicio 2 q0=aq1 q1=bq2+aq3λ q2=cq2+bq3λ = c* + bq3λ q3=cq4 q4=bq4+aq3λ = b* + aq3λ   Solución: q4=b* + aq3 q3=c(b*+a)* q2=c* + b(c(b* + a)*) q1=b(c* + b(c(b* + a))) + a(c(b + a)*) q0=b(c* + b(c(b* + a))) + a(c(b + a)*) Ejercicio 3 q0=mq1 + hq2λ q1=aq2λ + hq3λ q2=mq1 q3=aq3λ = a*λ   Solución: q3=a* q2=mq1 q1=a(m)* + h(a*) q0=m(a(m*)) + h(a*) + h(mq1)

Pasos para convertir un autómata a expresión regular Observa el autómata ·          Se analiza estado por estado o    Se lleva a una ecuación (Se pone el signo = ) ·          Se tiene que ver las dos palabras que tiene o    Si tomo el valor de uno de queda en q0 o    Si tomo el valor de cero se queda en q1 ·          Cuando llego a estado de aceptación es este caso q1 se pone épsilon ϵ (que acepta también el alfabeto vacío) solo cuando llegue al estado de aceptación. o    Si tomo el valor de 1 se queda en q1 o    Si tomo el valor de 0 se queda en q0 ·          Siempre que se repita el estado, se pone la palabra y la estrella de klin ·          Ya que tengo las ecuaciones se resuelve de abajo hacia arriba ·  ...

Expresiones regulares ·          Una descripción completa y fácil de leer de un lenguaje regular. ·          Usamos operadores para denotar constructores de lenguajes y construir lenguajes complejos a partir de lenguajes “atómicos” sencillas. Ejemplo: ·          La curp es una expresión regular. ·          El motor de búsqueda de Google es una expresión regular. Sinónimo de autómata finito - MaquinaEstadoFinito Es el estado final - Aceptacion Función en la que se basa un autómata - Transicion Finalidad del af al reconocer lenguajes de este tipo - Regulares Los lenguajes regulares pertenecen a estos lenguajes formales - Formales Se representa con la letra sigma - Alfabeto Es el primer estado - Inicial Puntos donde se desplazará el autómata - Estado Representación simbólica de un estado finito - Grafo

Fases de un compilador Compilador Es un programa traductor cuya función es traducir (compilar) un programa fuente escrito en algún lenguaje de alto nivel a lenguaje máquina. Este programa traducido o programa objeto, normalmente es guardado en memoria secundaria en forma ejecutable y es cargado a memoria principal cada vez que requiera ser ejecutado. Intérprete Al igual que el compilador, el intérprete traduce un programa fuente escrito en algún lenguaje de alto nivel, pero con la diferencia que cada instrucción es ejecutada inmediatamente, sin generar un programa en lenguaje de máquina. En general la compilación es un proceso más eficiente que la interpretación. Esto se debe a que las sentencias dentro de un ciclo deben ser reinterpretadas cada vez que se ejecutan por un intérprete. En cambio, con un compilador, cada sentencia es traducida a lenguaje de máquina sólo una vez. Ensamblador es un tipo de lenguaje de bajo nivel utilizado para escribir programas informáticos, y constituye l...

Estructura de un traductor 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. 1. Ejemplos de traductores son los ensambladores y los compiladores. 2. En el proceso de traducción se identifican dos fases principales: 3. Fase de análisis 4. Fase de Síntesis

Lenguajes, tipos y herramientas Lenguaje: Subconjunto del universo del discurso. Conjunto de palabras de un determinado alfabeto. "El alfabeto Σ es también un lenguaje sobre Σ." Lenguaje vació: Es aquel que no contiene la cadena vacía ni ninguna otra cadena.     Cardinal ( { Ø } ) = 0     Cardinal ( { λ } ) = 1 Clausula (cierre) positiva de un lenguaje: El lenguaje obtenido uniendo el lenguaje L con todas sus potencias posibles, excepto L0. Obviamente, ninguna clausura positiva contiene la palabra vacía, a menos que dicha palabra esté en L. Puesto que el alfabeto Σ es también un lenguaje sobre Σ, puede aplicársele esta operación. Se verá entonces que: L+ = L1 U L2 U L3.... W(∑) = Lenguaje universal de ∑. ∑+ = W(∑) - { λ } Estrella de kleene: Es la unión de todas las potencias de un lenguaje incluso L0. Obviamente, todas las clausuras contienen la palabra vacía. Son evidentes las siguientes identidades: L0 = λ L* = L+ U { λ } L* =L0 U L1 U L2 U L3..... Puest...