Código	9317	Descripción
Crdts. Teor.	3	MÁQUINAS SECUENCIALES Y AUTÓMATAS FINITOS. GRAMÁTICAS Y LENGUAJES FORMALES. REDES NEURONALES.
Crdts. Pract.	1,5
A efectos de intercambios en programas de movilidad, la carga de esta asignatura equivale a 5,62 ECTS.

Departamentos y Áreas
Departamentos	Área	Crdts. Teor.	Crdts. Pract.	Dpto. Respon.	Respon. Acta
LENGUAJES Y SISTEMAS INFORMÁTICOS	LENGUAJES Y SISTEMAS INFORMATICOS	3	1,5

Estudios en los que se imparte

Ingeniería Técnica en Informática de Gestión - plan 2001

Pre-requisitos

FUNDAMENTOS DE PROGRAMACIÓN II

Incompatibilidades de matrícula por contenidos equivalentes
Sin Datos

Matriculados (2009-10)

Sin Datos

Ofertada como libre elección (2009-10)

Sin departamento

Consulta Gráfica de Horario

Pincha aquí

Horario (2009-10)
Modo	Grupo (*)	Día inicio	Día fin	Día	Hora inicio	Hora fin	Aula
CLASE TEÓRICA	1	14/09/2009	23/12/2009	L	12:00	14:00	A2/C24
	2	14/09/2009	23/12/2009	X	15:00	17:00	A2/E03
PRÁCTICAS CON ORDENADOR	1	14/09/2009	23/12/2009	X	15:00	16:00	0016P1006
	2	14/09/2009	23/12/2009	X	16:00	17:00	0016P1006
	3	14/09/2009	23/12/2009	X	17:00	18:00	0016P1006

(*) CLASE TEÓRICA
	1: GRUPO 1 - CAS
	2: GRUPO 2 - CAS
(*) PRÁCTICAS CON ORDENADOR
	1: GRUPO Prácticas de LGA-01 - CAS
	2: GRUPO Prácticas de LGA-01 - CAS
	3: GRUPO Prácticas de LGA-01 - CAS

Grupos de matricula (2009-10)
Grupo (*)	Cuatrimestre	Turno	Idioma	Distribución (letra nif)
1	1er.	M	CAS	desde A hasta M
2	1er.	T	CAS	desde N hasta Z

(*) 1: GRUPO 1 - CAS

(*) 2: GRUPO 2 - CAS

Objetivos de las asignatura / competencias (2009-10)

Generales Que el alumno se familiarice con las teorías formales para la descripción de lenguajes naturales y artificiales. El conocimiento de algunos problemas en los que dichas teorías tienen aplicación o que han motivado su construcción. La adquisición de herramientas básicas necesarias para algunas asignaturas. El desarrollo de la capacidad de abstracción y análisis teórico en relación con la teoría de lenguajes. Fundamentales Diferenciar y clasificar los distintos lenguajes de acuerdo con la jerarquía de Chomsky. Saber construir (algorítmicamente y también de forma intuitiva en los casos sencillos) autómatas finitos para el reconocimiento y análisis de lenguajes regulares. Conocer el funcionamiento de un traductor secuencial y saber cómo se transforma una máquina de Mealy en un máquina de Moore y viceversa. Saber obtener el autómata mínimo para un lenguajes regular dado. Saber definir mediante una gramática lenguajes sencillos, en particular, el lenguaje reconocido por un autómata finito determinista. Dominar algunas técnicas elementales de transformación de gramáticas: cómo eliminar la recursión por la izquierda, cómo reescribirlas en forma normal de Chomsky. Conocer algún algoritmo (por ejemplo, el de Cocke, Younger y Kasami) para discriminar frases admisibles de un lenguaje que ha sido definido mediante una gramática independiente del contexto.

Contenidos teóricos y prácticos (2009-10)

Bloque 1: Autómatas finitos y lenguajes regulares. Tema 1: Nociones básicas de teoría de conjuntos. 1.1. Conjunto. Definiciones y propiedades. 1.2. Correspondencias y relaciones. 1.3. Cardinal. Conjuntos infinitos. 1.4 Conjuntos numerables. Propiedades y ejemplos. 1.5. Conjuntos no numerables. Ejemplos. Tema 2: Lenguajes y computadores. 2.1. Alfabetos y lenguajes. 2.2. Lenguajes y computadores. 2.3. Problemas y lenguajes. Tema 3: Autómatas finitos. 3.1. Definición y representaciones de un autómata finito determinista (AFD). 3.2. El AFD como clasificador. Ejemplos. 3.3. Lenguaje aceptado por un AFD. 3.4. El AFD como traductor. Máquinas de Moore y de Mealy. 3.5. Autómatas finitos indeterministas (AFI). Ejemplos. 3.6. Lenguaje aceptado por un AFI. 3.7. Autómatas finitos estocásticos. Ejemplos. Tema 4: Expresiones y lenguajes regulares. 4.1. Definición de expresión regular (ER). Ejemplos 4.2. Propiedades de las ER. 4.3. Equivalencia entre ER y autómatas finitos. Tema 5: Propiedades de los lenguajes regulares 5.1. Propiedades de clausura de los lenguajes regulares. 5.2. Algoritmos y decidibilidad. 5.3. Equivalencia y minimización de autómatas. 5.4. Lema del bombeo para lenguajes regulares. Bloque 2: Gramáticas y lenguajes independientes del contexto. Tema 6: Gramáticas y lenguajes independientes del contexto. 6.1. Definición y notación de las gramáticas. 6.3. Lenguaje generado por una gramática y tipos de gramáticas. 6.4. Gramáticas regulares. Ejemplos. 6.5. Gramáticas independientes del contexto (GIC). Ejemplos. 6.6. Análisis sintáctico (algoritmo de Cocke, Younger y Kasami). 6.7. Simplificación de GIC. 6.8. Formas normalizadas de Chomsky y Greibach.

Más información

Profesor/a responsable

Mico Andres , Maria Luisa

Metodología docente (2009-10)

Clases teóricas

Clases magistrales. También se plantearán ejercicios referentes a la teoría.

Tipo de actividades: teóricas y prácticas

Laboratorios

Implementación de autómatas finitos y analizadores léxicos a partir de expresiones regulares. Se supone el conocimiento del lenguaje C ó C++.

Profesores (2009-10)
	Grupo	Profesor/a
TEORIA COMPARTIDA DE 9317 Y 9360	1	Marco Such, Manuel
		Mico Andres, Maria Luisa
	2	Mico Andres, Maria Luisa
PRÁCTICAS CON ORDENADOR DE 3164	1	Sánchez Navarro, Jose Luis
	2	Sánchez Navarro, Jose Luis
	3	Sánchez Navarro, Jose Luis

Enlaces relacionados

http://www.dlsi.ua.es/asignaturas/lga/applet/Afapplet.html

Bibliografía

Ordenar por título del libro Ordenar por profesor que lo recomienda

Introducción a la teoría de autómatas, lenguajes y computación Autor(es): Hopcroft, John E. ; Motwani, Rajeev Edición: Madrid : Addison-Wesley, 2008. ISBN: 978-84-7829-088-8 Recomendado por: MICO ANDRES, MARIA LUISA (*1) [ Acceso al catálogo de la biblioteca universitaria ] [ Acceso a las ediciones anteriores ] Teoria d`autòmats i llenguatges formals Autor(es): Ferri, Francesc J. Edición: Valencia : Publicacions de la Universitat de València, 2004. ISBN: 84-370-1806-4 Recomendado por: MICO ANDRES, MARIA LUISA [ Acceso al catálogo de la biblioteca universitaria ] Teoría de autómatas y lenguajes formales Autor(es): Kelley, Dean Edición: Madrid : Prentice Hall, 1995. ISBN: 0-13-518705-2 Recomendado por: MICO ANDRES, MARIA LUISA (*1) [ Acceso al catálogo de la biblioteca universitaria ] Teoría de la computación : lenguajes formales, autómatas y complejidad Autor(es): BROOKSHEAR, J. Glenn Edición: México : Pearson Educación, 1999. ISBN: 968-444-384-6 Recomendado por: MICO ANDRES, MARIA LUISA (*1) [ Acceso al catálogo de la biblioteca universitaria ] [ Acceso a las ediciones anteriores ] Teoría de lenguajes, gramáticas y autómatas para informáticos Autor(es): Carrasco Jiménez, Rafael C., Calera Rubio, Jorge, Forcada Zubizarreta, Mikel L. Edición: Alicante : Universidad de Alicante, 2000. ISBN: 84-7908-574-6 Recomendado por: MICO ANDRES, MARIA LUISA (*1) [ Acceso al catálogo de la biblioteca universitaria ]

(*1) Este profesor ha recomendado el recurso bibliográfico a todos los alumnos de la asignatura.

Fechas de exámenes oficiales (2009-10)
Convocatoria	Grupo (*)	fecha	Hora inicio	Hora fin	Aula(s) asignada(s)	Observ:
Exámenes extraordinarios de finalización de estudios (diciembre)	-1	30/10/2009	12:00	15:00	A2/B11	-
Periodo ordinario para asignaturas de primer semestre	-1	26/01/2010	09:00	12:00	EP/S-09G 0039PS003 EP/S-02M	-
Periodo extraordinario de julio	-1	08/07/2010	08:30	11:30	A2/D11 A2/D12	-

(*) 1: GRUPO 1 - CAS

(*) 2: GRUPO 2 - CAS

Instrumentos y criterios de evaluación (2009-10)

Examen final

Nota final = 80% examen de teoría + 20% prácticas, aprobadas independientemente. El examen contendrá, al menos, un 40% de preguntas relativas a los objetivos fundamentales de la asignatura.