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.
|