Automatas

SEP SEIT DGIT

INSTITUTO TECNOLÓGICO DE CERRO AZUL

APUNTES DE :

LENGUAJES Y AUTOMATAS I

LENGUAJES Y AUTÓMATAS I

Prólogo.

El principal objetivo al escribir estos apuntes, fue desarrollar un material introductorio con un enfoque de programación para la materia de Lenguajes y Autómatas, mismo que fuera claro y comprensible. Este material además de informativo, remarca la importancia de la construcción de los autómatas como herramientas para su aplicación en la traducción de lenguajes de programación y de la codificación de compiladores.

Los apuntes de Lenguajes y autómatas, son una herramienta orientada a los profesores y alumnos que cursan la materia de Lenguajes y Autómatas que se imparte en la carrera de Ingeniería de Sistemas de los distintos Institutos Tecnológicos del país. El contenido de este material requiere de los conocimientos previos de la materia de Matemáticas Discretas en sus temas de Teoría de Conjuntos, Funciones de Computo, Relaciones Binarias, Teoría de grafos, teoría de árboles.

El objetivo que persigue el curso de Lenguajes y autómatas, es dar a los alumnos las bases teóricas matemáticas para desarrollar y optimizar software de base y construir procesos de reconocimiento de patrones, con esta finalidad, en este material se analizan cada uno de los diferentes modelos de autómatas, se analiza uno de los modelos más importantes de la teoría de la Computación: la Máquina de Turing.

Este material esta diseñado de tal forma que se mantiene la atención del estudiante centrada en un conjunto de problemas y ejercicios específicos que los ayudan a concebir las propiedades de los modelos, capacitándose para que en un momento dado escriban programas que los simulen

Este material es suficiente para el curso básico de Lenguajes y autómatas I a ser cubierto en un semestre, además será útil en programas que continúen con un curso de compiladores o de Programación de Sistemas I.

Contenido.

Introducción..................................................................................................................................1

TEMA 1 INTRODUCCION A LA TEORIA DE LENGUAJES ..........................................2

1.1 Alfabeto……………………...................................................................................................3

1.2 Cadenas…………………………...........................................................................................4

1.3 Lenguajes…………………………………………………………………………………….5

Gramáticas.............................................................................................................................10

Estructuras de las gramáticas.................................................................................................11

1.4 Tipos de Lenguajes ………………………...........................................................................17

Bibliografía..................................................................................................................................130

Introducción.

El objetivo que persigue todo lenguaje es la comunicación, ya sea con otras personas o con las computadoras. Para poder entendernos entre dos o más personas, es necesario que ambas conozcan el mismo lenguaje y el significado de las palabras. Las computadoras no son la excepción de este requerimiento, por lo que para escribir programas de computadoras, tanto el programador como la computadora deben comprender el lenguaje en el que se escriben dichos programas.

Ya que la computadora no cuenta con el mismo lenguaje que los humanos, se ha hecho necesario la creación de lenguajes de programación, los cuales deben ser muy precisos y deben ser ajustados a reglas fijas. Este trabajo trata de dar a conocer las reglas y símbolos de los lenguajes formales convenientes para la comunicación con las computadoras.

La estructura lexicográfica de un lenguaje es la forma de sus tokens. La sintaxis describe las declaraciones que serán aceptadas como correctas en un compilador o interprete para el lenguaje. La sintaxis, o precisamente lo que constituye una declaración válida, está definida por una gramática que genera un lenguaje formal. Un lenguaje formal es el conjunto de declaraciones que en un contexto sintáctico son correctas.

Una gramática implica una lista finita de símbolos llamado alfabeto, un conjunto de reglas para formar palabras y quizá otro conjunto de reglas para formar declaraciones con las palabras.

Cuando se habla de un lenguaje formal, nos estamos refiriendo a su forma o sintaxis de las palabras que serán válidas en el lenguaje, y no a si estas tienen un significado (semántica), por lo que las reglas formales para la generación y reconocimiento de los lenguajes de computadora son más sintácticas que semánticas.

Unidad Temática 1.

Introducción a la Teoría de Lenguajes Formales.

1.1. Alfabeto.

Antes de definir a un alfabeto empezaremos por conocer algunos conceptos básicos aplicables en toda la unidad.

Conjunto es una colección bien definida de objetos llamados elementos o miembros del conjunto. Por ejemplo el conjunto de todas las sillas de madera.

Una forma de describir un conjunto con un

...