Examen
- Describa la importancia de los compiladores en la actualidad desde el punto de vista teórico y práctico. (10 puntos).
Los compiladores sirven en la práctica para facilitar la entrega de un lenguaje objetivo -ensamblador, traducción binaria, sintesís de hardware, …- programamos en un lenguaje fuente porque suele ser más llevadero su uso, y en el caso de los más avanzados significan oportunidades de demostrar que el lenguaje objetivo funciona según espeficaciones, optimizarlo más de allá de lo que puede un programador, y otro tipo de compiladores pueden ayudar a otras áreas como matemáticas a realizar demostraciones.
Desde un punto de vista teórico son la oportunidad de comprobar los límites de la computación (complejidad, teoría de automátas, computabilidad) y lograr resultados superiores por la dinámica de continua retroalimentación entre teoría y práctica debido a que compilador es un proyecto aplicado de teoría de la computación.
- Mencione dos coincidencias y dos diferencias entre Intérpretes y Compiladores. Incluya dos ejemplos de cada uno de ellos utilizados en la actualidad. (10 puntos).
Compilador | Intérprete | |
Coincidencia | * Sistema de lenguaje de procesamiento. * Bien conocido como implementarlo. | * Sistema de lenguaje de procesamiento. * Bien conocido como implementarlo. |
Diferencia | * Executa las operaciones después de la traducción. * Suele tener como salida un lenguaje objetivo (ensamblador). | * Executa las operaciones durante la traducción. * No suele tener como salida un lenguaje objetivo. |
Ejemplo | gcc,clang | V8 (JavaScript engine), SpiderMonkey |
- Considerando el alfabeto , especifique para cada uno de los siguientes lenguajes la expresión regular que lo denota: (20 puntos)
- El conjunto de todas las cadenas en las cuales las secuencias “000” y “111” no aparecen.
Para este ejercicio se necesita aquellas cadenas menores a 3 caracteres que cumplan lo solicitado tales como 0, 1, 11, , 00 concadenadas con aquellas cadenas de 3 y 2 caracteres que no pueden llevarnos a esas cadenas como -caso base- y con estrella de Kleene recursivamente.
b. El conjunto de todas las cadenas que representen números binarios pares.
Entiendo que un número binario par es un número binario que cumple con , donde .
Los números binarios terminando en 0 son números binarios pares.
Demostración.
Sea un número binario donde sea su longitud, tenemos que
Donde si y , si .
Pero nosotros queremos , así
Para
Si alguna entones que es par por definición y al ser un elemento neutro no afecta lo que sigue.
Donde si y , si .
por lo que existe, de lo que sigue que sería demostrar.
La expresión regular es:
c. El conjunto de todas las cadenas binarias representando números mayores a ocho.
Para este ejercicio se requiere que la cadena binaria
Precisamente toads las cadenas binarias tales que , esto implica que por uebos son aquellas cadenas que ignoran el inicio con 0 (las cadenas binarias son posicionales), todas las cadenas de tamaño mayores a o iguales a 9 -- y al final cualquier cadena binaria.
Así la expresión regular es:
- Proporcione el DFA que acepte todas las cadenas binarias que representan números mayores a ocho decimal. (15 puntos).
Por el ejercicio anterior sabemos la expresión regular que representa este problema, solo es cuestión de cambiar de representación: DFA.
Al dividir tres máquinas , , y estas son concatenedas forman la siguiente máquina:
- Mencione las etapas que componen la estructura de un compilador y una breve descripción de cada una de ellas. (15 puntos)
Use la funcionalidad de «zoom» con confianza: esto no se pixelea.
- Indique cuál es el lenguaje que acepta el siguiente DFA, proporcione la expresión regular correspondiente y elabore el NFA equivalente. (20 puntos)
Procedimiento:
1.
- Usando Generalizado NFA convertimos a expresión regular:
Obtemos el lenguaje:
Usando la expresión convertimos a NFA (siguiendo el algoritmo de Thompson, donde el ‘.’ signifca concatenación):
- Revelamos la concatenación
(0|1.(0.1*.0)*.1)*
- De prefija postfija.
0 1 0 1 * . 0 . * . 1 . | *
- Para este ejercicio en particular cree un intérprete de expresiones regulares [2] [3] usando el «McNaughton–Yamada–Thompson algorithm»[1]
0 1 0 1 * . 0 . * . 1 . | *
Flujo de ejecución
# El primero estado de la máquina es el estado inicial (qi < qn, donde n es el resto de estados).
# El último estado de la máquina es el estado final (qF > qn, donde n es el resto de estados).
# Guardamos de cada máquina el estado inicial y el estado final.
# El estado de aceptación se determina al finalizar el ciclo.
# Creamos las máquinas básicas y las almacenamos en una pila (de abajo a arriba)
M1 q0 --> q1: 0
M2 q2 --> q3: 1
M3 q4 --> q5: 0
M4 q6 --> q7: 1
Pila: M1, M2, M3, M4
# Por precedencia '*' es ejecutado antes, lo que implica que
# la máquina en el tope de la pila es sustituida por otra máquina
# con la operación de conversión en mente
M5
q8 --> q9: lambda
q6 --> q7: 1
q8 --> q6: lambda
q7 --> q8: lambda
Pila: M1, M2, M3, M5
# Seguimos con '.', este operador necesita dos máquinas que une el último estado
# de la máquina con el primero de la segunda máquina.
M6
q4 --> q5: 0 # M3
q5 --> q8: lambda
q8 --> q9: lambda # M5
q6 --> q7: 1
q8 --> q6: lambda
q7 --> q8: lambda
Pila: M1, M2, M6
# Otro estado básico
M7
q10 --> q11: 0
Pila: M1, M2, M6, M7
# El resto del ciclo
...
# Al final el tope de la pila será la máquina que buscamos
# Donde el estado final es el estado de aceptación
[1] Ken Thompson (Jun 1968). "Programming Techniques: Regular expression search algorithm". Communications of the ACM. 11 (6): 419–422. doi:10.1145/363347.363387. S2CID 21260384.
[2] Theory of computation. (2022, September 04). Retrieved from https://theory-of-computation-uabc.sanchezcarlosjr.com/app/#/automata/DbIJPWJiBrm3PuiZ0vZS
[3] sanchezcarlosjr. (2022, September 04). theory-of-computation. Retrieved from https://github.com/sanchezcarlosjr/theory-of-computation
- Indique cuál es el lenguaje que acepta el siguiente NFA y elabore el DFA equivalente. (20 puntos)
De lo que se sigue
El DFA equivalente es: