1.- DATOS DE LA ASIGNATURA

Nombre de la asignatura: Lenguajes y Autómatas

Carrera: Ingeniería en Sistemas Computacionales

Clave de la asignatura: SCB-9324

Horas teoría-Horas práctica-Créditos: 4-0-8

2. U B 1 C A C I O N D E L A A S 1 G N A T U R A

a) RELACION CON OTRAS ASIGNATURAS DEL PLAN DE ESTUDIO

ASIGNATURAS Y TEMAS ANTERIORES (REQUISITOS):

Matemáticas Discretas Teoría de conjuntos

Funciones de Cómputo

Relaciona Binarios

ASIGNATURAS Y TEMAS POSTERIORES:

Inteligencia Artificial Representación interna

de la Inteligencia Artificial

LISP

Visión de la I.A.

Análisis Sintáctico

Deducción y Lógica

Comprensión del Lenguaje

Organización de la memoria

b) APORTACIONDE LA ASIGNATURAAL PERFIL DEL EGRESADO

Esta materia proporcionará las bases teóricas matemáticas para desarrollar y optimizar

Software de base.

3. O B JET 1 V O (S) G E N E R A L (ES) DEL C U R S O

Al finalizar el curso, el alumno comprenderá el funcionamiento de los Lenguajes y la

Teoría de Autómatas.

4. T E M A R I O.

I.- Introducción:

1.1 Conjuntos fini~os e infinitos - Alfabeto- Propiedades de String

a) Longitud

b) Concatenación - Lenguaje

1.2 Representación finita del lenguaje.

II.- Gramáticas:

2.1 Introducción a las gramáticas

2.2 Estructuras de las gramáticas

2.3 Clasificación de las gramáticas (CHOMSKI)

- Contexto sensitivo - Sensible del contexto - Libre de contexto -

Estructura de fase

2.4 Representación de gramáticas - Notación de BNF

- Diagramas sintácticos.

III.- Autómatas finitos:

3.1 Autómatas finitos deterministicos (AFD)

3.2 Autómatas finitos no deterministicos (AFND)

3.3 Equivalencia de AFND y AFD

3.4 Propiedades de los lenguajes aceptados por un autómata finito.

3.5 Autómatas finitos y expresiones regulares.

3.6 Determinación de lenguajes regulares y no regulares.

IV.- Autómata de push-down:

4.1 Definición.

4.2 Lenguajes aceptados por autómata PUSH-DOWN.

4.3 PDA deterministico.

4.4 PDAY CFL.

V.- Máquina de Turing:

5.1 Definición de máquina de Turing.

5.2 Funcionamiento de la máquina de Turing.

5.3 Lenguajes aceptados por la máquina de Turing.

5.4 Ejemplo de mayor fuerza de la máquina de Turing.

5.5 Extensiones de la máquina de Turing.

5.6 Máquina de Turing no deterministica.

5.7 El problema HALFING para las máquinas de Turing.

VI.- Gramáticas y Autómatas:

6.1 Lenguajes regulares. - Teorema de Kleene

- Las aplicaciones del lema de Pumping

– El teorema MGHILL nerode.

6.2 Lenguajes de contexto libre

- Forma normal EHUMSKG

- Lema de BARHILL el Pumping - Autómata de Pushdawn

- Compilador de lenguajes formales

- Lenguajes Brackat.

6.3 Lenguajes de contexto sensitivo - Autómata lineal Bounded - Aspectos prácticos -

Ejemplificación con un lenguaje conocido.

VII Aplicaciones a lenguajes:

7.1 Objetivos y filosoffa de diseño de lenguajes de programación.

- Comunicación humana

- Prevensióny detención - Utilidad - Eficiencia - Independencia de la máquina -

Simplicidad - Uniformidad - Otras fiilosoffas del diseño.

7.2 Disño detallado

- Microestructuras

- Estructuras de expresión - Estructura de datos - Estructuras de control

- Estructuras del compilador - Estructura l/O.

5. A P R E N D I Z A J E S R E Q U E R I D O S

Matemáticas Discretas

6. S U G E R E N C I A S D I D A C T I C A S

- Presentar el análisis de gramáticas, autómatas o máquinas de Turing con aplicaciones a lenguajes comerciales.

- Que el alumno investigue las estructuras sintácticas y léxicas de un lenguaje comercial con la finalidad de aplicarlos a un lenguaje diseñado por él.

7. S U G E R E N C I A S D E E V A L U A C I O N

- El alumno investigará la estructura de lenguajes comerciales.

- El alumno presentará resultados de sus investigaciones mediante la exposición ante el grupo.

- Aplicación de exámenesescritos.

NOTA: Los dos puntos anteriores deberán ser elaborados y enriquecidos por la Academia,

en coordinación con el Departamento de Desarrollo Académico.

8. U N I D A D E S D E A P R E N D I Z A J E

NUMERO DE UNIDAD: I

NOMBRE DE LA UNIDAD: INTRODUCCION

OBJETIVO EDUCACIONAL:
Definirá, distiguirá y reconocerá los elementos básicos de lenguajes.

ACTIVIDADES DE APRENDIZAJE:

1.1.- Distinguir entre conjuntos finitos e infinitos.

1.2.- Reconocer e identificar las características del lenguaje y del alfabeto.

1.3.- Extrapolar un alfabeto.

NUMERO DE UNIDAD: II

NOMBRE DE LA UNIDAD: GRAMATICAS.

OBJETIVO EDUCACIONAL:

Definirá, distinguirá y reconocerá los elementos de una gramática.

ACTIVIDADES DE APRENDIZAJE:

2.1.- Comprenderá que es una gramática.

2.2.- Adquirirá los elemntos principales de la gramática.

2.3.- Análisis de la clasificación.

2.4.- Representar grámaticas.

NUMERO DE UNIDAD: III

NOMBRE DE LA UNIDAD: AUTOMATAS FINITOS.

OBJETIVO EDUCACIONAL:

Adquirirá los conocimientos necesarios para la aplicación de los autómatas en la construcción de lenguajes.

ACTIVIDADES DE APRENDIZAJE:

3.1.- Reconocer un autómata finito deterministico.

3.2.- Reconocerá un autómata finito no deterministico.

3.3.- Traducir un AFND a un AFD.

3.4.- Deducir su lenguaje regular.

3.5.- Relación entre autómatas finitos y expresiones regulares.

3.6.- Diferenciar entre un lenguaje regular y uno ambiguo.

NUMERO DE UNIDAD: IV

NOMBRE DE LA UNIDAD: AUTOMATAS PUSH-DOWN.

OBJETIVO EDUCACIONAL:

Adquirirá los conocimientos necesarios sobre autómatas Push-Down en el análisis y construcción de un lenguaje.

ACTIVIDADES DE APRENDIZAJE:

4.1.- El alumno conocerá las partes y funcionamiento de un PDA como dispositivo determínistico para el reconocimiento de un lenguaje.

4.2.- El alumno analizará los casos de lenguajes aceptados por un PDA y por un CFL.

NUMERO DE UNIDAD: V

NOMBRE DE LA UNIDAD: MAQUINAS DE TURING.

OBJETIVO EDUCACIONAL:

Explicará el funcionamiento de la Maquina de Turing.

ACTIVIDADES DE APRENDIZAJE:

5.1.- Conocer los elementos, funcionamiento y aplicación de la máquina de Turing.

NUMERO DE UNIDAD: VI

NOMBRE DE LA UNIDAD: GRAMATICAS Y AUTOMATAS.

OBJETIVO EDUCACIONAL:

Creará y desarrollará lenguajes en base a gramáticas y autómatas.

ACTIVIDADES DE APRENDIZAJE:

6.1.- Conocerá teoremas para el diseño de lenguajes.

6.2.- Conocerá obras gramaticales para la creación de lenguajes.

NUMERO DE UNIDAD: VII

NOMBRE DE LA UNIDAD: APLICACIONES A LENGUAJES.

OBJETIVO EDUCACIONAL:

Diseñará un lenguaje.

ACTIVIDADES DE APRENDIZAJE:

7.1.- Identificará los criterios de diseño de un lenguaje.

7.2.- Aprenderá el diseño detallado de lenguajes.

9. BIBLIOGRAFIA BASICA Y COMPLEMENTARIA:

1.- Hopcroft, John and Ullman Jeffrey

Introduct;on to Automatas Theor Languages and Computation

Addisson-Wesley, Mass. 1979.

2.- Harry R.Lewis, Chistas H. Papadimitrion.

Elementos of the Theory of Computat;on

Prentice-Hall, Ing. 1981.

3.- V.S.Rayward-Smith.

A First Course in Formal Language Theory.

4.- Hartin D. Davis and Elaine J. Weyuker.

Computability, Complexity, and Languages.

Fundamentales of teoret;cal Computer Sc;ence.

Academic preess, Ing. 1983.