automatas

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.

Conjuntoes 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 finitode 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 esimportante, 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 puedenser 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 (oelementos) 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 elconjunto 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 conjuntode 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 que1 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 eluso 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...