Los Automatas

Unidad I: Introducción a la teoría de la Computación

Tema1: Conceptos Preliminares
Objetivo:
* El alumno recordará y aplicará las operaciones básicas de conjuntos así como definirá los elementos de un lenguaje. Además conocerá la clasificación de las gramáticas.
1.1. CONJUNTOS.
Un conjunto es una colección de objetos llamados elementos del conjunto. Si A es un conjunto y a es unelemento de A utilizaremos la notación a Î A (se lee "a es un elemento de A"). Se usa la notación bÏ A cuando b no es un elemento de A.
Si A contiene exactamente los elementos a1, a2, ..., an, lo indicamos escribiendo A= {a1, a2, ..., an}.
Un conjunto sólo se caracteriza por sus elementos y no por el orden en el cual se listan.
Los conjunto A y B son iguales si contienen los mismos elementos. Por lotanto si, A={1,2,3} y B={2,1,3} se puede escribir que A = B.
Algunas veces es conveniente describir el contenido de un conjunto en términos de una propiedad que sea característica de todos los elementos del conjunto. Sea P(x) una proposición sobre x. La notación {x| P(x)}, que se interpreta como "el conjunto de todas las x tales que P(x)", denota el conjunto de todos los x para los cuales P(x) esuna proposición verdadera. (Todas las x tienen la propiedad P).

1.2. OPERACIONES CON CONJUNTOS.
Las operaciones habituales que se definen sobre los conjuntos son:
El conjunto Æ llamado conjunto vacío o nulo, no tiene elementos. El conjunto vacío es un subconjunto de todos los conjuntos.
La unión de conjuntos A y B se denota por A È B y es un conjunto formado por los elementos que aparecen enA, en B o en ambos.
Por lo tanto A È B ={x|xÎ A ó x Î B}.
Por ejemplo, si A={1, 2, 3} y B= {a, b}, entonces A È B={1, 2, 3, a, b}.
La intersección de A y B es el conjunto de todos los elementos que aparecen simultáneamente en A y también en B.
Por lo tanto A Ç B ={x|xÎ A y x Î B}.
Por ejemplo, si A={1, 4, 5, 7} y B= {2, 4, 7, 8}, entonces A Ç B={4, 7}.
El complemento relativo si A y B sondos conjuntos cualesquiera, el complemento de B con respecto a A es el conjunto: A-B={x|xÎ A y xÏ B}.
Por lo tanto, A-B esta compuesto por todos los elementos de A que no están también en B. Por ejemplo, si A={0, 2, 4, 6, 8, 10} y B={0,1, 2, 3, 4}, entonces A-B={6, 8, 10}, mientras que B-A={1, 3}.
2A , el conjunto potencia de A, es el conjunto formado por todos los subconjuntos de A. Por ejemplo,sea A={a, b, c} . Entonces 2A ={Æ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.
Dados dos conjuntos A y B, su producto cartesiano, AxB, es el conjunto de todos los pares ordenados de los que el primer elemento proviene de A y el segundo de B. Así que, AxB ={(a, b)|aÎ A y bÎ B}. Por ejemplo, sí A={1,2,3} y B={5,6} entonces: AxB ={(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)}.
Si A y B sonconjuntos y todos los elementos de A son también elementos de B, se escribe A Í B y se dice que A es un subconjunto de B. Por ejemplo A={1,2,3} y B={0,1,2,3,4,5} , se tiene A Í B. Por otro lado, B no es un subconjunto de A, porque los elementos 0, 4 y 5 de B no lo son de A.
La Inclusión cuando cualquier elemento de A que este en B, o cualquier elemento de B que este en A, ó que sean iguales. Por ejemplosi A={2, 4, 5, 7, 8} y B={2, 4}, entonces AÌ B={2, 4}.
La cardinalidad de un conjunto es el número de elementos de ese conjunto. Por ejemplo si A={a, b} entonces |A|=2. La cardinalidad del conjunto vacío es 0 porque no tiene ningún elemento.
Todos los conjuntos aquí tratados se consideran subconjuntos de un conjunto universal U. Los complementos pueden ser formados con respecto a este conjuntouniversal. Si A es un conjunto, entonces U- A es el conjunto de todos los elementos que no están en A. Conviene denotar tales complementos mediante A, de forma que U- A = A. Obsérvese que Æ =U y U = Æ .
1.3. ALFABETOS.
Un alfabeto es un conjunto no vacío y finito de símbolos. En el caso del alfabeto inglés, la colección finita es el conjunto de las letras del alfabeto junto con los símbolos que...