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 número finito de elementos es enlistarlos entre llaves. Así todo el conjunto de todos los enteros positivos menores de cuatro se pueden escribir como: {1, 2, 3}.

El orden en que los elementos se enlisten no es importante, de allí que {1, 2, 3}, {3, 2, 1}, {3, 1, 2}, {2, 1, 3} y {2, 3, 1} sean todos representaciones del mismo conjunto. Los términos repetidos en el listado de los elementos del conjunto pueden ser ignorados, así {1, 3, 2, 3, 1}, es otra representación del mismo conjunto.

Se usan letras mayúsculas como A, B, C, S, T,..., para indicar el conjunto y letras minúsculas para indicar miembros (o elementos) de los conjuntos. Se indica el hecho de que x es un elemento del conjunto S escribiendo x  S, y se indica el hecho de que x no es un elemento del conjunto S escribiendo x  S.

Si el conjunto de elementos es muy extenso, el conjunto puede describirse por las propiedades de sus elementos utilizando la notación { | }.

Ejemplo 1:

{n | n  N y n es par}, representa el conjunto de todos los enteros pares no negativos, es decir el conjunto {0, 2, 4, 6, 8, 10, ...,}

Ejemplo 2:

{x | x  R y 1  x  3}, es el conjunto de todos los números reales mayores o iguales que 1 y menor que 3.

Otra forma de especificar un conjunto es a través de la siguiente notación {n  N | n es par}, {x  R |1  x  3}, ó especificar un conjunto enumerando sus elementos mediante el uso de otro conjunto de elementos.

Ejemplo 3:

{n2 | n  N }, es el conjunto de todos los enteros que son cuadrados de enteros en N, es decir {n2 | n  N } = {m  N | m = n2 para alguna n  N } = {0, 1, 4, 9, 16, 25, 36…}.

Considerando que S y T son dos conjuntos, se dice que T es subconjunto de S si todo elemento de T pertenece a S y se escribe T  S.

Los conjuntos pueden tener un tamaño finito o infinito, por ejemplo: el conjunto de los números enteros mayores que cero y menores que tres es un conjunto finito que consta de los elementos 1 y 2. Por otro lado el conjunto de los números enteros mayores a cero es un conjunto infinito. Para poder determinar el tamaño de un conjunto, es necesario contar con una medida para este propósito. Tal medida es la llamada cardinalidad de un conjunto.

Cardinalidad de un conjunto.

La cardinalidad de un conjunto A, es el número de elementos del conjunto y se denota por card(A) o por |A|. La cardinalidad puede ser finita o infinita. Cuando el conjunto es finito, basta con contar sus elementos para determinar su cardinalidad. Sin embargo, la situación se complica cuando hablamos de conjuntos infinitos.

Un símbolo es una entidad abstracta que no se define formalmente. Usualmente, los símbolos se denotan usando las letras a, b, c, d y e.

Un alfabeto es un conjunto finito no vacío de símbolos y se denota por .

1.2. Cadenas.

Una cadena o palabra es una secuencia de símbolos s = a1, a2 ,…, an donde ai  . Para denotar las cadenas se utilizan, generalmente, las letras s, t, u, v, w.

Al conjunto de todas las palabras que utilizan símbolos de  se denotan como * (sigma estrella, ó cerradura de Kleene). Cada subconjunto de * se llama lenguaje sobre .

Ejemplo 4:

Sea  = {a,b,c,d,…,z} las letras del alfabeto castellano. Cualquier secuencia de

...