Sintaxis

U.T.N.- F.R.T.

Cátedra “SINTAXIS Y SEMÁNTICA DE LOS LENGUAJES”

Dpto. de I.S.I. 6to. llamado Diciembre 2010 Apellido y Nombre:

Examen Final
Nro.Legajo:

1) Verdadero/Falso a) Los LenguajesRecursivos son cerrados con respecto a la operación de complemento. b) El problema de pertenencia siempre tiene solución para Lenguajes Irrestrictos. c) Para todo ALL no-determinista existe una MTdeterminista equivalente. d) El problema de determinar si una GIC es ambigua tiene una solución algorítmica. e) La cantidad de transiciones de un “castor afanoso” en relación a la cantidad de estadosdel mismo es una función Turing Computable.

2) Dado el Esquema de Traducción, emparejar cada regla con la acción correspondiente:
REGLA DE SINTÁXIS ACCIONES SEMÁNTICAS

P→D;S D → boolean id D →otrotipo id E→ verdadero E→ falso E→ otrovalor S → S1 ; S2 S→A S→W

1

2 3 4 5 6 7 8 9

W→ while E do S endwhile A → id = E

10 11

{Si (S1.tipo == ok) ∧ (S2.tipo == ok) entonces S.tipo = oksino S.tipo = error-tipo } { id.tipo = 1 } {Si (id.tipo == E.tipo) entonces A.tipo = ok sino A.tipo = error-tipo } { E.tipo = 1} {S.tipo = W.tipo} { E.tipo = 2} {NULA} {S.tipo = A.tipo} {Si (E.tipo ==1) ∧ (S.tipo == ok) entonces W.tipo = ok sino W.tipo = error-tipo } { E.tipo = 1} { id.tipo = 2 }

3) Dado el Sistema Canónico, emparejar cada componente con la denominación correspondiente:Componente 0 1 X 2 Código 3
1 dígito yx

├─ 0 dígito ├─ 1 dígito x dígito ├─ x código x dígito ; y código ├─ yx código

Denominación
Término Predicado Variable Terminal Remarca

4 5

4) Dado elsiguiente Autómata de Pila responder: a) Criterio de aceptación: Por estado final Por pila vacía b) Criterio de análisis: Descendente Ascendente c) El símbolo inicial de la pila es: S y estáinicialmente en la pila # y no está inicialmente en la pila d) La GIC asociada está en formato estándar de: Greibach Chomsky e) Describir la GIC asociada. f) Describir el LIC aceptado. 5) Dado el siguiente...