Examen

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

    💡
    “Los límites de mi lenguaje significan los límites de mi mundo”, Wittgenstein, Tractatus Logico-Philosophicus.

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.

  1. 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).
CompiladorInté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.
Ejemplogcc,clangV8 (JavaScript engine), SpiderMonkey
💡
Para lo que sigue, usamos la notación de POSIX extendida para escribir expresiones regulares.
  1. Considerando el alfabeto Σ={0,1}\Sigma=\{0,1\}, especifique para cada uno de los siguientes lenguajes la expresión regular que lo denota: (20 puntos)
    1. 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, ϵ\epsilon, 00 concadenadas con aquellas cadenas de 3 y 2 caracteres que no pueden llevarnos a esas cadenas como 001,01,10,110001,01,10,110 -caso base- y con estrella de Kleene recursivamente.

    (0010110110)(0111ϵ00)(001|01|10|110)^*(0|1|11|ϵ|00)

    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 n2n_2 que cumple con 2k10=n102k_{10}=n_{10}, donde k10Nk_{10}\in N.

    Los números binarios terminando en 0 son números binarios pares.

    Demostración.

    Sea n2n_2 un número binario donde mm sea su longitud, tenemos que

    n2=xmxm1...x0:=i=0mf(xi)n_2=x_mx_{m-1}...x_0:=\sum_{i=0}^{m}f(x_i)

    Donde f(xi)=0,f(x_i)=0, si xi=0x_i=0 y f(xi)=2if(x_i)=2^i, si xi=1x_i=1.

    Pero nosotros queremos x0=0x_0=0, así

    n2=xmxm1...0:=i=0mf(xi)n_2=x_mx_{m-1}...0:=\sum_{i=0}^{m}f(x_i)

    Para 2k10=i=0mf(xi)=f(x0)+f(x1)+f(x2)+f(x3)+...+f(xm)2k_{10}=\sum_{i=0}^{m}f(x_i)=f(x_0)+f(x_1)+f(x_2)+f(x_3)+...+f(x_m)

    Si alguna xi=0x_i=0 entones f(xi)=0f(x_i)=0 que es par por definición y al ser un elemento neutro no afecta lo que sigue.

    2k10=0+f(x1)+f(x2)+f(x3)+...+f(xm)=2(f1(x1)+f1(x2)+f1(x3)+...+f1(xm))2k_{10}=0+f(x_1)+f(x_2)+f(x_3)+...+f(x_m)\\ =2(f_1(x_1)+f_1(x_2)+f_1(x_3)+...+f_1(x_m))\\

    Donde f1(xi)=0f_1(x_i)=0 si xi=0x_i=0 y f1(xi)=2i1f_1(x_i)_=2^{i-1}, si xi=1x_i=1.

    por lo que k10k_{10} existe, de lo que sigue que sería demostrar.

    La expresión regular es:

    (01)0(0|1)^*0

    c. El conjunto de todas las cadenas binarias representando números mayores a ocho.

    Para este ejercicio se requiere que la cadena binaria n2:=n10>8n_2:=n_{10}>8

    Precisamente toads las cadenas binarias tales que n2:=10019n_2:=1001\ge9, 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 -1001,1010,1011,1100,...1001,1010,1011,1100,...- y al final cualquier cadena binaria.

    Así la expresión regular es:

    0(10011000(01)101(01)110(10)111(10))(01)0^*(1001|1000(0|1)|101(0|1)|110(1|0)|111(1|0))(0|1)^*
  1. 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 L(M2)=0L(M_2)=0^*, L(M2)=(10011000(01)101(01)110(10)111(10))L(M_2)=(1001|1000(0|1)|101(0|1)|110(1|0)|111(1|0)), L(M3)=(01)L(M_3)=(0|1)^* y estas son concatenedas forman la siguiente máquina:

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

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

  1. Usando Generalizado NFA convertimos a expresión regular:

Obtemos el lenguaje: L(M)=(01(010)1)L(M)=(0|1(01^*0)^*1)^*

Usando la expresión convertimos a NFA (siguiendo el algoritmo de Thompson, donde el ‘.’ signifca concatenación):

  1. Revelamos la concatenación
(0|1.(0.1*.0)*.1)*
  1. De prefija postfija.
0 1 0 1 * . 0 . * . 1 . | *
  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

  1. Indique cuál es el lenguaje que acepta el siguiente NFA y elabore el DFA equivalente. (20 puntos)

NFA con estado de error.

De lo que se sigue L(M)=ab+aL(M)=ab^+a

El DFA equivalente es: