Modulo Automates Y Lenguajes Formales

INTRODUCCIÓN

Autómatas y lenguajes formales es un curso de carácter teórico, que se inscribe

en el campo de formación profesional básico del Programa de Ingeniería de

Sistemas con un valor académico de tres créditos.

El estudiante en el desarrollo de este curso demuestra la asimilación de los

conceptos y mecanismos fundamentales para la definición de lenguajes

(expresiones regulares, gramáticas independientes del contexto y gramáticas

generales), los tres tipos de máquinas correspondientes para su reconocimiento

(autómatas finitos, autómatas a pila y maquinas de Turing) y las propiedades

fundamentales de las familias de lenguajes por ellos definidas, también realiza el

estudio de las condiciones necesarias para que un lenguaje sea de un tipo

determinado.

El curso es principalmente teórico, jugando un papel secundario la implementación

de algoritmos. Al final del curso el estudiante debe demostrar la asimilación de los

conceptos fundamentales mediante la resolución de problemas acerca de los

mismos, así como la realización de algunas prácticas en el computador.

Este curso toma como base el avance de los lenguajes de programación de alto y

bajo nivel para propiciar la distinción entre lenguajes formales con reglas

sintácticas y semánticas rígidas, concretas y bien definidas, de los lenguajes

naturales como el inglés o el español, donde la sintaxis y la semántica no se

pueden controlar fácilmente. Los intentos de formalizar los lenguajes naturales,

lleva a la construcción de gramáticas, como una forma de describir estos

lenguajes, utilizando para ello reglas de producción para construir las frases del

lenguaje. Se puede entonces caracterizar un lenguaje mediante las reglas de una

gramática adecuada.

Los temas sobre autómatas, computabilidad, e incluso la complejidad algorítmica

fueron incorporándose al currículo de ciencias de la computación de diferentes

universidades desde la década de los 60, esta incorporación puso de manifiesto

que las ciencias de la computación habían usado gran cantidad de ideas de muy

diferentes campos para su desarrollo, y que la investigación sobre aspectos

básicos podía cooperar y aumentar los avances de la computación.

Como elemento determinante en el curso es importante que se tengan en cuenta

los conceptos matemáticos básicos de teoría de conjuntos, funciones, relaciones y

principios fundamentales de la lógica, ya que éstos temas no son tratados como

temáticas en el módulo, pero que tienen gran importancia en el curso.

...