Teoria de la computacion

Capitulo 1
En este capítulo se incluyen los conceptos de grafos, árboles, conjuntos, relaciones, cadenas, lenguajes abstractos e inducción matemática.

* Cadenas, alfabetos y lenguajes

Un símbolo es una entidad abstracta; las letras y los dígitos son ejemplos de símbolos usados con frecuencia. Una cadena (o palabra) es una secuencia finita de símbolos yuxtapuestos. La longitud de unacadena w, es el número de símbolos que componen la cadena.

Los prefijos de una cadena están formados por los primeros símbolos de esta, y los sufijos, por los últimos. Un prefijo o sufijo de una cadena que no sea la misma cadena es un prefijo o sufijo propios.

La concatenación de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacios entreellas. La yuxtaposición de usa como el operador de concatenación.

Un alfabeto es un conjunto finito de símbolos. Un lenguaje es un conjunto de cadenas de símbolos tomados de algún alfabeto.

* Grafos y arboles

Un grafo, denotado por G = (V, E), consiste en un conjunto finito de vértices V y un conjunto de pares de vértices E llamados aristas.

* Grafos dirigidos

Un grafodirigido, que también se denota como G = (V, E), consiste en un conjunto finito de vértices V y un conjunto de pares ordenados de vértices E, llamados arcos.

* Arboles

Un árbol (estrictamente hablando, un árbol dirigido y ordenado) es un dígrafo que posee las siguientes propiedades

1. Existe un vértice, llamado raíz, que no tiene predecesores y del cual parte una trayectoria hacia cadavértice.
2. Cada vértice, diferente de la raíz, tiene exactamente un predecesor.
3. Los sucesores de cada vértice están ordenados “a partir de la izquierda”.

Se deberán dibujar los arboles con la raíz en la cima y todos los arcos apuntando hacia abajo.
* Notación de conjuntos

Un conjunto es una colección de objetos sin repetirse. Los conjuntos finitos pueden hacerse haciendouna lista de sus elementos. También especificamos a los conjuntos como un formador de conjuntos:

{x | P (x)}

Esta proposición se lee “el conjunto de objetos x de modo que P(x) es verdadera” en la que P(x) es alguna proposición sobre los objetos x; ó

{x en A | P(x)}

Se lee “el conjunto de x objetos del conjunto A de modo que P(x) es verdadera”, y es equivalente a:

{x | P(x) y x esta enA}.

Si cada elemento de A es elemento de B, entonces escribimos A B, y diremos que A esta contenido en B.

A B es lo mismo que B A.

Si A B pero A B, es decir, cada elemento de A esta en B y existe algún elemento de B que no está en A, entonces escribiremos A B.

Los conjuntos A y B son iguales si tienen los mismos elementos. Esto es A = B si y solo si A B y BA.

*Operaciones con los conjuntos

1. A B, la unión de A con B es: {x | x esta en A o x esta en B}

2. A B, la intersección de A y B es: {x | x esta en A y x esta en B}

3. A – B, la diferencia de A y B es: {x | x esta en A y x no está en B}

4. A x B, el producto cartesiano de A y B, es el conjunto de pares ordenados (a, b) tales que a esta en A y b esta en B.

5. 2A, el conjuntopotencia de A, es el conjunto formado por todos los subconjuntos de A.

* Relaciones

Una relación es un conjunto de pares. El primer componente de cada par se toma de un conjunto llamado dominio, y el segundo componente de cada par pertenece a un conjunto llamado contradominio. Si R es una relación de (a, b) es un par en R, se denota la relación como aRb.

* Propiedades de lasrelaciones

1. Reflexiva si aRa para toda a en S
2. Irreflexiva si aRa es falsa para toda a en S
3. Transitiva si aRb y bRc implican aRc
4. Simétrica si aRb implica bRa
5. Asimétrica si aRb implica que bRa es falsa

Capitulo 2

* Sistemas de estados finitos

El autómata finito es un modelo matemático de un sistema, con entradas y salidas discretas. El sistema puede...