Entradas

3: Autómatas Finitos

Autómatas Finitos El término máquina evoca algo hecho en metal, usualmente ruidoso y grasoso, que ejecuta tareas repetitivas, que requieren de mucha fuerza o velocidad o precisión. Ejemplos de estas máquinas son las embotelladoras automáticas de refrescos. Su diseño requiere de conocimientos en mecánica, resistencia de materiales y hasta dinámica de fluidos. Al diseñar tal máquina, el plano en que se le dibuja hace abstracción de algunos detalles presentes en la máquina real, tales como el color con que se pinta, o las imperfecciones en la soldadura. El término máquina evoca algo hecho en metal, usualmente ruidoso y grasoso, que ejecuta tareas repetitivas, que requieren de mucha fuerza o velocidad o precisión. Ejemplos de éstas máquinas son las embotelladoras automáticas de refrescos. Su diseño requiere de conocimientos en mecánica, resistencia de materiales y hasta dinámica de fluidos. Autómatas Finitos (2) Al diseñar tal máquina, el plano en que se le dibuja hace abstracción de algu...
Publicar un comentario
Leer más

6 Análisis Sintáctico

Imagen
6.1 Funciones del analizador sintáctico. En el modelo del compilador, el analizador sintáctico obtiene una cadena de componentes léxicos del analizador léxico, y comprueba si la cadena puede ser generada por la gramática del programa fuente. En nuestro  modelo de compilador, el analizador sintáctico obtiene una cadena de tokens del analizador léxico, como se muestra en la figura, y verifica que la cadena de nombres de los tokens pueda generarse mediante la gramática para el lenguaje fuente. Esperamos que el analizador sintáctico reporte cualquier error sintáctico en forma inteligible y que se recupere de los errores que ocurren con frecuencia para seguir procesando el resto del programa. De manera conceptual, para los programas bien formados, el analizador sintáctico construye un árbol de análisis sintáctico y lo pasa al resto del compilador para que lo siga procesando. De hecho, el árbol de análisis sintáctico no necesita construirse en forma explícita, y a que las accion...
Publicar un comentario
Leer más

5 Análisis léxico

Imagen
5.1 Funciones del analizador léxico. Un  analizador léxico  o  analizador  lexicográfico (en inglés scanner) es la primera fase de un compilador consistente en un programa que recibe como entrada el código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes  léxicos ) o símbolos. Conceptos: Un  token  es un par que consiste en un nombre de token y un valor de atributo opcional. El nombre del token es un símbolo abstracto que representa un tipo de unidad léxica; por ejemplo, una palabra clave específica o una secuencia de caracteres de entrada que denotan un identificador. Los nombres de los tokens son los símbolos de entrada que procesa el analizador sin táctico. A partir de este momento, en general escribiremos el nombre de un token en negrita. Con frecuencia nos referiremos a un token por su nombre. • Un  patrón  es una descripción de la forma que pueden tomar los lexemas...
Publicar un comentario
Leer más

4: Máquinas de Turing.

4.1 Definición formal MT La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo. (MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta , borrando el símbolo , escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendo esto según se ind...
Publicar un comentario
Leer más

2 Expresiones Regulares.

Imagen
2.1. Definición formal de una ER. Es un equivalente algebraico para un autómata. Utilizado en muchos lugares como un lenguaje para describir patrones en texto que son sencillos pero muy útiles. Pueden definir exactamente los mismos lenguajes que los autómatas pueden describir: Lenguajes regulares. Ofrecen algo que los autómatas no: Manera declarativa de expresar las cadenas que queremos aceptar. Dado un alfabeto Dado un alfabeto Σ, una , expresión regular sobre expresión regular sobre Σ se define de forma recursiva: ER primitivas:  Φ , λ, {a | a  ЄЄЄ  Σ  Є } Si α y β son ER, entonces son también ER: α + β (unión), α β (concatenación), α* (cierre), (α). No existen otras reglas para la construcción de ER sobre Σ. Ejemplos de usos. Comandos de búsqueda, e.g., grep de UNIX. sistema de formato de texto: Usan notación de tipo expresión regular para describir patrones. Convierte la expresión regular a un DFA o un NFA y simula el autómata en el ar...
1 comentario
Leer más

1 Lenguajes Formales.

Imagen
1.1    Alfabeto Un alfabeto es un conjunto finito no vacío cuyos elementos se llaman símbolos. Denotamos un alfabeto arbitrario con la letra Σ. Símbolos: Es una entidad abstracta que no se puede definir, ya que se dejaría como una axioma. Igual que se define un punto en la geometría. La cual normalmente los símbolos son letras (a, b, c,…. z), dígitos (0,1,…9, caracteres (+, -, *, /,>,< …..). los símbolos pueden estar formados por varias letras o caracteres. Alfabeto: El alfabeto o abecedario es un conjunto de letras, con un determinado orden. podríamos precisamente decir que el alfabeto es un conjunto de letras (caracteres o grafemas) de un sistema de escritura, cada una representa aproximadamente un fonema (consonante o vocal). 1.2 Cadenas. Una cadena o palabra sobre un alfabeto Σ. admitimos la existencia de una única cadena que no tiene símbolos, la cual se denomina cadena vacía y se denota con λ. la cadena vacía desempeña, en la teoría de lenguajes ...
Publicar un comentario
Leer más