Código	9176	Descripción
Crdts. Teor.	3	MAQUINAS SECUENCIALES Y AUTOMATAS FINITOS. GRAMATICAS 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 en Informática - plan 2001

Pre-requisitos

FUNDAMENTOS DE PROGRAMACIÓN II

Incompatibilidades de matrícula por contenidos equivalentes
Sin Datos

Matriculados (2009-10)
Grupo (*)	Número
1	40
2	33
3	3
TOTAL	76

(*) 1: GRUPO 1 - CAS

(*) 2: GRUPO 2 - CAS

(*) 3: GRUPO 3 Valenciano - VAL

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	X	09:00	11:00	A2/D23
	2	14/09/2009	23/12/2009	L	16:30	18:30	A2/D23
	3	14/09/2009	23/12/2009	L	10:00	12:00	A3/0013
PRÁCTICAS CON ORDENADOR	1	14/09/2009	23/12/2009	X	18:00	19:00	0016P1006
	2	14/09/2009	23/12/2009	V	13:00	14:00	0016P1006
	3	14/09/2009	23/12/2009	V	14:00	15:00	0016P1006

(*) CLASE TEÓRICA
	1: GRUPO 1 - CAS
	2: GRUPO 2 - CAS
	3: GRUPO 3 Valenciano - VAL
(*) PRÁCTICAS CON ORDENADOR
	1: Grupo de Prácticas de LGA 9176 - CAS
	2: Grupo de Prácticas de LGA 9176 - CAS
	3: Grupo de Prácticas de LGA 9176 - 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
3	1er.	M	VAL	desde - hasta -

(*) 1: GRUPO 1 - CAS

(*) 2: GRUPO 2 - CAS

(*) 3: GRUPO 3 Valenciano - VAL

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 DE 9176	1	Calera Rubio, Jorge
		Mico Andres, Maria Luisa
	2	Marco Such, Manuel
		Mico Andres, Maria Luisa
	3	Marco Such, Manuel
		Mico Andres, Maria Luisa
PRÁCTICAS CON ORDENADOR DE 9176	1	Sánchez Navarro, Jose Luis
	2	Marco Such, Manuel
	3	Marco Such, Manuel

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

Introduction to languages and the theory of computation Autor(es): John C. Martin Edición: New York [etc.] : McGraw-Hill, cop.2003. ISBN: 0-07-119854-7 (International ed.) Recomendado por: MICO ANDRES, MARIA LUISA [ Acceso al catálogo de la biblioteca universitaria ] 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 (*1) [ Acceso al catálogo de la biblioteca universitaria ] Teoría de lenguajes, gramáticas y autómatas para informáticos Autor(es): Rafael C. Carrasco Jiménez, Jorge Calera Rubio, Mikel L. Forcada Zubizarreta Edición: Alicante: Publicaciones de la Universidad de Alicante. ISBN: 84-7908-574-6 Recomendado por: MICO ANDRES, MARIA LUISA [ 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	0039PS003 EP/S-09G 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

(*) 3: GRUPO 3 Valenciano - VAL

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.