Práctica 2 (Paradigmas)

Ejercicio 1

Determinar qué expresiones son sintácticamente válidas (es decir, pueden ser generadas con las gramáticas presentadas) y determinar a qué categoría pertenecen (expresiones de términos o expresiones de tipos):

a) x ---------VALIDO, expresiones de términos

b) x x ---------VALIDO, expresiones de términos

c) M --------- No es un término

d) M M --------- No es un término

e) true false ---------VALIDO, expresiones de términos

f) true succ(false true) ---------VALIDO, expresiones de términos

g) λx.isZero(x) --------- Falta tipo

h) λx: σ. succ(x) --------- Falta tipo, sigma no es un tipo valido

i) λx: Bool. succ(x) ---------VALIDO, expresiones de términos

j) λx: if true then Bool else Nat. x --------- Falta tipo

k) σ --------- Sigma no es un tipo valido

l) Bool ---------VALIDO, expresiones de tipos

m) Bool → Bool ---------VALIDO, expresiones de tipos

n) Bool → Bool → Nat ---------VALIDO, expresiones de tipos

ñ) (Bool → Bool) → Nat ---------VALIDO, expresiones de tipos

o) succ true --------- Si succ fuera una variables seria una aplicación, pero el enunciado dice que las variables se representan con una letra por lo cual a succ como termino le faltan los paréntesis.

p) λx: Bool. if 0 then true else 0 succ(true) ---------VALIDO, expresiones de términos

Ejercicio 2

Mostrar un término que utilice al menos una vez todas las reglas de generación de la gramática y exhibir su árbol sintáctico.

   (λx: Bool. if isZero(succ(pred(x))) then true else false) x
       app                  /                                  \
   (λx: Bool. if isZero(succ(pred(x))) then true else false)    x
    abs         /
   if isZero(succ(pred(x))) then true else false
   ITF     /                       |          \
   isZero(succ(pred(x))            true        false
          /
   succ(pred(x))
        /
   pred(x)
      / 
     x

Ejercicio 3

a) Marcar las ocurrencias del término x como subtérmino en λx: Nat. succ((λx: Nat. x) x).

b) Ocurre x1 como subtérmino en λx1 : Nat. succ(x2)?

c) Ocurre x (y z) como subtérmino en u x (y z)?