Download Lenguajes formales

UNIVERSIDAD CAECE
DEPARTAMENTO DE SISTEMAS
PROGRAMA DE:
LENGUAJES FORMALES
CODIGO DE LA CARRERA
078
AÑO
4º
CARRERA:
PLAN DE LA CARRERA
CODIGO ASIGNATURA
CUATRIMESTRE
VIGENCIA
10
1º
7329/10S
2010
INGENIERIA EN SISTEMAS
Nº DE RESOLUCIÓN MINISTERIAL
819/02
Nº DE RESOLUCIÓN INTERNA
846/01 – 808/03-027/10
OBJETIVOS
Que los alumnos:
• Conozcan los fundamentos teóricos de la Informática.
• Manejen los métodos para la definición sintáctica de los lenguajes de programación:
regulares, independientes de contexto y gramáticas con atributos.
• Se familiaricen con los algoritmos para la construcción, modificación, y optimización de
autómatas finitos, autómatas de pila y máquinas de Turing.
• Adquieran los conceptos básicos de computabilidad.
• Utilicen métodos de verificación de correctitud de programas y definición semántica de
un lenguaje
CONTENIDOS MINIMOS
Teoría de Lenguajes. Gramáticas regulares, libres del contexto y dependiente del
contexto. Gramáticas equivalentes. Teoría de autómatas. Relación entre las gramáticas y
los autómatas. Máquinas de Turing. Computabilidad. Correctitud de Algoritmos.
UNIVERSIDAD CAECE
1
PROGRAMA ANALITICO
1.
LENGUAJES REGULARES
Alfabetos. Sartas y lenguajes. Operaciones.
Expresiones regulares.
Autómatas finitos.
Gramáticas regulares.
Analizadores léxicos.
2.
LENGUAJES INDEPENDIENTES DE CONTEXTO
Gramáticas independientes de contexto.
Derivación, ambigüedad, transparencia.
Autómata de Pila.
Analizadores sintácticos.
3.
LENGUAJES DE TIPO MÁS GENERAL
Gramáticas sensibles al Contexto.
Lenguajes estructurados en frase.
Gramáticas con atributos.
4.
COMPUTABILIDAD
Máquinas de Turing.
Máquina Universal.
Computabilidad, decibilidad, enumerabilidad recursiva.
Límites de los sistemas formales.
5.
CORRECTITUD
Floyd:.aserciones.
Hoare:.lógica de Hoare.
Dijkstra: Programación disciplinada.
BIBLIOGRAFÍA
Alfonseca Cubero E., Alfonseca Moreno M. y Moriyón Salomón R. (2007). Teoría de
Lenguajes Gramáticas y Autómatas. Madrid Mc-Graw Hill
BIBLIOGRAFÍA COMPLEMENTARIA
Brookshear (1993). Teoría de la Computación, Lenguajes formales, autómatas y
complejidad. México: Adisson Wesley Iberoamericana.
Hopcroft (1993). Introducción a la teoría de autómatas, lenguajes y computación.
México: Compañía editora Continental.
Isasi, Martínez, Borrajo (1997). Lenguajes, gramáticas y autómatas, un enfoque
práctico. México: Adisson Wesley Iberoamericana.
Martín (1995). Lenguajes formales y sus autómatas. En Presser, Cárdenas y Marín:
Ciencias de la computación. México: Limusa Wiley.
Brokshear (1993). Teoría de la Computación, lenguajes formales
complejidad. México: Adisson Wesley Iberoamericana
UNIVERSIDAD CAECE
autómatas y
2
METODOLOGÍA
Metodología expositiva - participativa, con apoyo bibliográfico, guías de estudio teórico –
prácticas.
Actividades Teóricas
En la parte teórica se realizan exposiciones del docente orientadas a que el estudiante
participe activamente y desarrolle habilidades para permitir una mejor comprensión en
aquellos conceptos introductorios a la teoría de la computación.
Actividades de Formación Práctica
La parte práctica comprenderá, resolución de problemas, ejercicios y cuestionarios Se
pretende que en cada unidad el alumno desarrolle habilidades en el planteo y que
adquiera precisión en sus razonamientos.
DISTRIBUCION DE LA CARGA HORARIA
Horas %
1 Módulos/Semana = 4 horas
17 Semanas/Cuatrimestre = 68 horas
TEORIA
34
50
FORMACION PRÁCTICA:
0
0
• Experimental Laboratorio/Taller/Campo
34
50
• Resolución de Problemas
0
0
• Proyecto y Diseño
0
0
• PPS
Total Carga Horaria
68
100
EVALUACIÓN: APROBACIÓN DEL CURSADO DE LA ASIGNATURA
•
Cumplimiento del 75% de asistencia
•
Aprobación de las evaluaciones parciales de acuerdo a lo establecido en la
planificación de la materia que se anexa.
EVALUACIÓN FINAL: REGIMEN DE APROBACIÓN DE LA MATERIA
La evaluación final con un examen final oral y/o escrito, que comprenda la totalidad de los
contenidos estudiados durante el cuatrimestre.
FERNANDO LOPEZ GIL
Director Departamento
UNIVERSIDAD CAECE
MARIANA ORTEGA
Secretaria Académica
3