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,

...