LENGUAJES Y AUTOMATAS 1

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...

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...

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...

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...