UA
   LENGUAJES,GRAMÁTICAS Y AUTÓMATAS    Año académico       Versión PDF.  Versión PDF para convalidación.
Código9176Descripción
Crdts. Teor.3MAQUINAS 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ÁreaCrdts. Teor.Crdts. Pract.Dpto. Respon.Respon. Acta
LENGUAJES Y SISTEMAS INFORMÁTICOSLENGUAJES Y SISTEMAS INFORMATICOS31,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 (2011-12)
Grupo (*)Número
1 8
2 9
TOTAL 17
(*) 1: GRUPO 1 - CAS
(*) 2: GRUPO 2 - CAS
(*) 3: GRUPO 3 VALENCIANO - VAL


Ofertada como libre elección (2011-12)
Número máximo de alumnos: Sin límite
Pincha aquí para ver a qué estudios se oferta
Consulta Gráfica de Horario
A efectos de intercambios en programas de movilidad, la carga de esta asignatura equivale aPincha aquí


Horario (2011-12)
Sin horario


Grupos de matricula (2011-12)
Grupo (*)CuatrimestreTurnoIdiomaDistribució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


Otras distribuciones (2011-12)
Grupo Estudio
3 Se le asigna a Ingeniería en Informática - plan 2001


Objetivos de las asignatura / competencias (2011-12)
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 (2011-12)









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 (2011-12)
Clases teóricas
No existen clases presenciales.


Tipo de actividades: teóricas y prácticas
Laboratorios

Implementació de autòmats finits i analitzadors lèxics a partir d`expressions regulars (se suposa el coneixement d`un llenguatge de programació: C o C++).



Profesores (2011-12)
Grupo Profesor/a
TEORIA COMPARTIDA DE 9176, 9317 Y 93601MICO ANDRES, MARIA LUISA
2MICO ANDRES, MARIA LUISA
3FORCADA ZUBIZARRETA, MIKEL-LORENZO
MICO ANDRES, MARIA LUISA
PRÁCTICAS CON ORDENADOR COMPARTIDA DE 9176, 9317 Y 93601MICO ANDRES, MARIA LUISA
4MICO ANDRES, MARIA LUISA
Enlaces relacionados
http://www.dlsi.ua.es/asignaturas/lga/applet/Afapplet.html


Bibliografía

Introducción a la teoría de autómatas, lenguajes y computación
Autor(es):John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman ; traducción y revisión técnica, Manuel Alfonseca ... [et al.]
Edición:Madrid [etc.] : Addison Wesley, D.L. 2002.
ISBN:84-7829-056-7
Recomendado por:MICO ANDRES, MARIA LUISA
[ Acceso al catálogo de la biblioteca universitaria ]

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):Francesc J. Ferri
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 (2011-12)
ConvocatoriaGrupo (*)fechaHora inicioHora finAula(s) asignada(s)Observ:
Exámenes extraordinarios de finalización de estudios (diciembre) -1 04/11/2011 12:00 15:00 GB/1002 -
Periodo ordinario para asignaturas de primer semestre -1 18/01/2012 12:00 15:00 EP/S-09G -
Periodo extraordinario de julio -1 13/07/2012 14:30 17:30 EP/0-23G -
(*) 1: GRUPO 1 - CAS
(*) 2: GRUPO 2 - CAS
(*) 3: GRUPO 3 VALENCIANO - VAL


Instrumentos y criterios de evaluación (2011-12)
Examen final
Nota final = examen de teoría. El examen contendrá, al menos, un 40% de preguntas relativas a los objetivos fundamentales.