SIS - 762 Autmatas.
1
Tema N 1.
Introduccin a la teora de los autmatas
Introduccin.-
En cualquier lenguaje humano vemos que hay una serie de componentes que se repiten. Cada
lenguaje tiene su alfabeto, por ejemplo el alfabeto latino, el griego, el chino; concatenando smbolos se
forman las palabras y concatenando palabras se obtienen las frases.
Ahora bien, no basta concatenar palabras correctas para obtener frases, se deben seguir unas reglas de
sintaxis determinadas por la gramtica propia de cada lengua en cuestin. De manera que cuando
leemos un prrafo en una cierta lengua, pongamos en espaol, podemos detectar tres tipos de errores:
Puede ocurrir que encontremos smbolos que no pertenecen al alfabeto del espaol
Podra tambin ocurrir que tengamos faltas de ortografa, por ejemplo Baca
Por ltimo podemos encontrar que aunque las palabras sean todas en espaol una frase no
tenga sentido porque su sintaxis no es correcta, por ejemplo: yo tu entonces casa.
1.1 Teora de Conjuntos.
El fundamento ms importante para el estudio de los lenguajes y autmatas es la Teora de Conjuntos,
siempre que hablemos de formalizar una nocin, estaremos diciendo en realidad expresar en
trminos de la Teora de Conjuntos.
Definiciones bsicas.
Intuitivamente, un conjunto es una coleccin de objetos que por lo general se denominan elementos(o
miembros) del conjunto. Con frecuencia se emplea una notacin con llaves para describir un conjunto;
por ejemplo, podemos escribir A = {a, b, c} para indicar que A es el conjunto cuyos elementos son a, b, y
c. Otro ejemplo es W = {x: x es un numero positivo}, que se lee W equivale al conjunto de todos los x tal
que x es un entero positivo, lo cual indica que W es el conjunto de todos los enteros positivos. Un caso
algo especial es el conjunto vaco, representado por { } y tambin por, que no contiene elementos.
Los conjuntos pueden expresarse de dos maneras bsicamente:
En extensin, lo cual quiere decir que citamos explcitamente cada uno de sus elementos, como en el
conjunto {1, 3, 5} que contiene exactamente los nmeros 1, 3 y 5.
Por ejemplo:
Expresar en extensin el conjunto A= {x|x , x > 10}.
A= {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35...,}
En comprensin, dando una descripcin precisa de los elementos que forman parte del conjunto, en vez
de citarlos explcitamente.
SIS - 762 Autmatas.
2
Por ejemplo, el conjunto del punto anterior puede ser visto como A= { i N/impar(i), i < 6}, donde se
supone que los nmeros impares cumplen la condicin impar(i).
A = { 1, 3, 5}
Igualdad de conjuntos. Dos conjuntos A y B son iguales, A = B, si y slo si tienen los mismos elementos,
esto es, x A ssi x B.
Inclusin de conjuntos.
La notacin A B signica que el conjunto A est contenido en el conjunto B, o ms tcnicamente,
que A es subconjunto de B.
Por ejemplo, el conjunto {a, c} es subconjunto de {a, b, c}, indicado como {a, c} {a, b, c}. En otras
palabras, A B cuando siempre que x A, tenemos tambin x B.
Obsrvese que de acuerdo con esta definicin, A A para cualquier conjunto A: todo conjunto es
subconjunto de s mismo. Un caso extremo es el conjunto vaco, que es subconjunto de cualquier
conjunto.
A B (x)(x A x B
Operaciones con conjuntos.
Sean A y B conjuntos. Se denen las siguientes operaciones con los conjuntos:
Unin de conjuntos, denotada por A B, que contiene los elementos del conjunto A y tambin los del
conjunto B, es decir.
A B = {x/ x A o x B}
Por ejemplo:
{1, 2, 3} {3, 4} = {1, 2, 3, 4}. La unin de conjuntos es conmutativa.
Interseccin de conjuntos, escrita A B, que conene los elementos que pertenecen simultneamente
al conjunto A y al conjunto B, es decir, A B = {x|x A y x B}.
Por ejemplo, {1, 2, 3} {3, 4} = {3}. La interseccin es conmutativa y asociativa.
Diferencia de conjuntos, A B, que conene los elementos de A que no estn en B, esto es, A B = {x|x
A y x B}. Por ejemplo, {1, 2, 3} {3, 4} = {1, 2}.
La resta o diferencia de conjuntos no siempre le quita elementos al primer conjunto; por ejemplo {1,
2, 3} {4, 5} = {1, 2, 3}. La diferencia de conjuntos no es ni asociativa ni conmutativa.
Sea A= { a, b, c, d } y B = { a, b, c, g, h, i }
A - B= { d }
SIS - 762 Autmatas.
3
Complemento de un conjunto. Es un caso particular de la diferencia, cuando el primer conjunto es
considerado como el universo que contiene todos los elementos posibles.
Sea U un universo, entonces el complemento del conjunto A, denotada por A
c
contiene los elementos
del universo que no estn en A. Por ejemplo, si el universo son los nmeros naturales {1, 2, 3, . . .},
complemento de los nmeros pares son los nmeros nones: {2, 4, 6, . . .}
c
= {1, 3, 5, . . .}. Claramente A
A
c
= U, para todo conjunto A; adems, A A
c
= .
Sea U = {1, 2, 3, 4, 5, 6, 7, 8, 9}
A= {1, 3, 5, 7, 9} donde A
c
= U
El complemento de A estar dado por:
A
c
= {2, 4, 6, 8}
Potencia de un conjunto A, denotada como 2
A
, contiene como elementos a todos los subconjuntos de
A, esto es, 2
A
= {x|x A}. En otras palabras, 2
A
es un conjunto de conjuntos. Por ejemplo, 2
{1,2,3}
= {,
{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. Recurdese que el conjunto vaco siempre forma parte de todo
conjunto potencia.
La notacin 2
A
recuerda que el tamao del conjunto potencia de A es 2 elevado a la potencia del
tamao de A, esto es, |2A| = 2
|A|
.
Producto Cartesiano de dos conjuntos, A B, es el conjunto de pares ordenados (a, b) tales que a A y
b B.
Por ejemplo,
{1, 2} {3, 4, 5} = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}
El tamao de un producto cartesiano AB es |A| multiplicado por |B|, como se puede vericar en el
ejemplo anterior.
El producto cartesiano no es conmutativo, pues no es lo mismo un par (a, b) que uno (b, a), ni asociativo,
pues no es lo mismo (a, (b, c)) que ((a, b), c).
