Sea f una fórmula la representación en lenguaje de proposiciones de una frase declarativa, y una (sigma)-interpretación la asignación de los valores verdad o falso a los átomos de f, una fórmula es satisfactible si una asignación de valores de los átomos de f hace cierta la interpretación.
Una fórmula es una tautología si es cierta para cualquier interpretación de f.
Una contradicción es una interpretación de f que la hace falsa.
Explicar qué es un SAT-solver y dar ejemplos de problemas prácticos que se pueden resolver mediante SAT-solvers.
Un SAT-solver es un programa que tiene por entrada una fórmula en FNC (Forma Normal Conjuntiva), e indica si es satisfactible o no.
Ejemplos...
//
Definir los conceptos de variable libre y variable ligada en una fórmula de predicados, y dar ejemplos de variables libres y variables ligadas en una fórmula.
Una variable libre es aquella aparición de una variable que no está afectada por un cuantificador. En caso de estar afectada por un cuantificador, es una variable ligada.
Ejemplos:
∃x(Ry ∧ Rx)
Como se puede ver, la variable y no está afectada por ningún cuantificador, por lo tanto dicha variable es libre. Sin embargo, x sí que lo está, por lo tanto está ligada.
Sea ∑ el alfabeto de entrada de un autómata, la función de transición para cada estado de un autómata determinista devolverá una única salida (i.e. un estado) para cada símbolo de ∑.
Sin embargo, para un autómata indeterminista puede devolver múltiples estados para el mismo símbolo de ∑.
Definir autómatas indeterministas que reconozcan los identificadores de Java, y los números enteros.
//
Definir los conceptos de gramática incontextual y gramática ambigua, y explicar el interés de las gramáticas no ambiguas en el diseño de los compiladores.
Una gramática incontextual es una estructura G=(V, ∑, P, S) donde:
- V es un alfabeto cuyos elementos se les llama variables.
- ∑ es un alfabeto disjunto de V, a cuyos elementos se les llama símbolos términales.
- P es un subconjunto finito de V x ( V U ∑ )*, a cuyos elementos se les llama producciones o reglas.
- S ∈ V es la variable inicial.
Si u, v ∈ ( V U ∑ )*, v se deriva de u en un paso, en símbolos u ⇒ v, si obtenemos v a partir de u aplicando una producción de P.
Se puede representar la derivación de A *⇒ v de G como un árbol. Si existe más de un árbol de derivación para la misma gramática, entonces se dice que dicha gramática és ambigua.
Es necesario para un compilador que sólo exista un único árbol de derivación para cualquier formulación de la gramática, porque de no ser así, existirían múltiples interpretaciones para la misma fórmula, y no se podría llegar a interpretar dicha fórmula.
Explicar el interés de las gramáticas LL(1) en el diseño del analizador sintáctico de un compilador.
Son gramáticas incontextuales fáciles de construir, que nos permiten definir una tabla de análisis con la que poder interpretar la expresión resultante de un análisis léxico.
Explicar en qué consisten las tres fases del diseño de un compilador, y en qué fases se utilizan los autómatas deterministas, los autómatas con pila, y las gramáticas incontextuales.
Existen tres fases en el diseño de un compilador:
-
Análisis léxico:
En esta fase, se define un autómata determinista que interpretará el código fuente de un programa y lo convertirá en una serie de símbolos o categorías sintácticas.
-
Análisis sintáctico:
Durante esta fase, se usa un autómata con pila, el cual se habrá generado a partir de una gramática incontextual que define reglas que validan las expresiones resultantes del analizador léxico.
El autómata genera un árbol de derivación único.
-
Análisis semántico:
Habiéndo descompuesto el código fuente en un árbol durante el análisis sintáctico, se hacen comprobaciones semánticas (tipos de datos), resolución de referencias de objetos, o asignaciones definitivas (asegurarse que las variables que se declaran, están previamente asignadas).
Una fórmula es la representación en lenguaje de proposiciones de una frase declarativa.
Un átomo es una frase declarativa que no puede descomponerse en frases más simples.
Un literal es un átomo, o la negación de un átomo.
Una cláusula es una disyunción de literales.
Definir el concepto de fórmula en forma normal conjuntiva, y mostrar el algoritmo visto en clase para transformar cualquier fórmula proposicional en una fórmula en forma normal conjuntiva.
Una fórmula está en forma normal conjuntiva si es una conjunción de cláusulas.
Algoritmo para transformar una fórmula proposicional a FNC:
-
Aplicar:
φ ⇔ ψ ≡ ( φ → ψ ) ∧ ( ψ → φ )
φ ⇒ ψ ≡ ¬φ ∨ ψ
-
Aplicar:
¬¬φ ≡ φ
¬( φ ∨ ψ ) ≡ ¬φ ∧ ¬ψ
¬( φ ∧ ψ ) ≡ ¬φ ∨ ¬ψ
-
Aplicar:
φ ∨ ( ψ ∧ χ ) ≡ ( φ ∨ ψ ) ∧ ( φ ∨ χ )
φ ∧ ( ψ ∨ χ ) ≡ ( φ ∧ ψ ) ∨ ( φ ∧ χ )
Es la formula resultante de aplicar la Regla de la resolución sobre dos cláusular proposicionales φ1 y φ2.
Si en φ1 hay un literal ψ1, que es la concatenación de un literal ψ2 en φ2, se suprimen ψ1 y ψ2, y se toma la disyunción de las cláusular resultantes.
Sean φ1, φ2, ..., φn, φ fórmulas proposicionales, y sea ψ1 ∧ ψ2 ∧ ... ∧ ψk una FNC de φ1 ∧ φ2 ∧ ... ∧ φn ∧ ¬φ, entonces:
{ φ1, φ2, ..., φn } |= φ ⇔ { ψ1, ψ2, ..., ψk } R|= □
Definir el concepto de autómata determinista, y explicar su interés en programación y en el diseño de compiladores.
Un autómata determinista (AD) es una estructura M = (K, ∑, δ, q0, F) tal que:
- K es un conjunto finito y no vacío de estados.
- ∑ es el alfabeto de entrada.
- δ es una función de K x ∑ en K.
- q0 ∈ K es el estado inicial.
- F ∈ K es el conjunto de estados aceptadores.
En el diseño de un compilador, estos autómatas se usan para hacer un análisis léxico de un código fuente para convertirlos en símbolos interpretables por un analizador sintáctico posteriormente.
Definir autómatas indeterministas que reconozcan los identificadores de JAVA y los números enteros sin signo.
Un autómata con pila (AP) es una estructura M = (K, ∑, η, Δ, q0, F) tal que:
- K es un conjunto finito y no vacío de estados.
- ∑ es el alfabeto de entrada.
- η es el alfabeto de la pila.
- Δ es un conjunto finito de elementos de la forma ((p,a,b), (q,x)) donde p,q ∈ K, a ∈ ∑ U { λ }, b ∈ η U { λ }, y x ∈ η*
- q0 ∈ K es el estado inicial.
- F ∈ K es el conjunto de estados aceptadores.
En el diseño de los compiladores, los AP se usan en la fase de análisis sintáctico de un compilador, tras haber pasado inicialmente por un análisis léxico que convierte el código fuente de un programa en una série de símbolos computables por el AP.
Existen tres fases en el diseño de un compilador:
-
Análisis léxico:
En esta fase, se define un autómata determinista que interpretará el código fuente de un programa y lo convertirá en una serie de símbolos o categorías sintácticas.
-
Análisis sintáctico:
Durante esta fase, se usa un autómata con pila, el cual se habrá generado a partir de una gramática incontextual que define reglas que validan las expresiones resultantes del analizador léxico.
El autómata genera un árbol de derivación único.
-
Análisis semántico:
Habiéndo descompuesto el código fuente en un árbol durante el análisis sintáctico, se hacen comprobaciones semánticas (tipos de datos), resolución de referencias de objetos, o asignaciones definitivas (asegurarse que las variables que se declaran, están previamente asignadas).
Necesitamos una manera de poder expresar en un lenguaje más humano las acciones que tiene que hacer un ordenador, el cual sólo entiende código máquina. Si tuviéramos que usar el lenguaje máquina para poder implementar cualquier programa, tardaríamos cantidades ingentes de tiempo en implementarlo.
Sin embargo, si tenemos un lenguaje de programación que nos permite expresar nuestro programa con más facilidad y en menor tiempo, sí que compensa estudiar el diseño de un compilador que traduzca dicho código en un código máquina comprensible para el ordenador.