La teoría de la computación (TC) es una ciencia (rama de la matemática-computación) que centra su interés en el estudio y definición formal de los cómputos.He estado pensando en estos dias en la idea iniciar una especie de guía/curso/apuntes de teoría de la computación como archivero de textos importantes para mi que puedo ofrecerles, así que este es el principio de estos apuntes guardados que ahora salen a flote.
Se le llama cómputo a la obtención de una solución o resultado a partir de ciertos datos o entradas utilizando para ello un proceso o algoritmo.
Wikipedia.es [Teoría de la Computación]
Wikipedia.en [Theory of Computation]
Antes de entrar en materia, quisiera empezar con algo básico de matemáticas que debemos saber para adentrarnos en el mundo de los autómatas.
Conjuntos
El término conjunto puede ser definido como una colección de objetos, por ejemplo, un conjunto de hombres, un conjunto de discos, un conjunto de balones, etc. $latex \\displaystyle{A}$ cada objeto perteneciente a un conjunto se le denomina elemento o miembro. Si un grupo de hombres es un conjunto, y luis es un miembro de este, se dice que luis pertenece al conjunto de hombres y se representa de la manera $latex \\displaystyle{ luis \\in Hombres }$.
En dado caso de que luis no perteneciera al grupo de hombres (no me pregunten la razón), la manera de representarlo seria la siguiente: $latex \\displaystyle{ luis \otin hombres}$.
Si un conjunto N tiene ciertos elementos, por ejemplo, un conjunto de hombres tiene como miembros a luis, carlos, y alberto, para representar al conjunto matemáticamente (por medio de corchetes) diriamos: $latex \\displaystyle{ Hombres = \\{luis, carlos, alberto\\} }$
Nos hemos dado cuenta que los corchetes $latex \\displaystyle{\\{\\}}$ nos ayudan a representar a un conjunto, encerrando a los miembros de este entre ellos. Otra manera de representar a un conjunto de manera un poco mas general seria de la forma: $latex \\displaystyle{ N = \\{v :v\\ es\\ vocal\\} }$, donde $latex \\displaystyle{N}$ equivale al conjunto de toda $latex \\displaystyle{v}$, tal que $latex \\displaystyle{v}$ es una vocal, o bien, $latex \\displaystyle{N = \\{v|v\\ es\\ una\\ vocal\\}}$, donde $latex \\displaystyle{ v | v\\ es\\ vocal }$ se lee "el conjunto de todas las v tal que v sea una vocal".
Podemos clasificar a los conjuntos en dos tipos, mismos que dependen de su cardinalidad. La cardinalidad de un conjunto es el numero de elementos que tiene, en el ejemplo de $latex \\displaystyle{Hombres = \\{luis, carlos, alberto\\}}$, la cardinalidad de $latex \\displaystyle{Hombres}$ es 3 y se representa de la forma $latex \\displaystyle{\\|Hombres\\|=3}$. La división es pues en conjuntos finitos y conjuntos infinitos. Un conjunto es finito siempre y cuando su cardinalidad sea conocida, sea esta 0 (conjunto vacío) o $latex \\displaystyle{N}$, sin embargo, si la cardinalidad no es conocida se dice que este conjunto es infinito.
Un conjunto $latex \\displaystyle{A = \\{n \\in N : 1 \\leqslant n \\leqslant\\} }$ es equivalente al conjunto $latex \\displaystyle{B = \\{1,2,3,4\\} }$ por lo que decimos que $latex \\displaystyle{A=B}$
Un conjunto $latex \\displaystyle{A = \\{1,2,3\\} }$ es distinto a $latex \\displaystyle{B = \\{4,5,6\\} }$ y lo representamos como $latex \\displaystyle{ A \eq B }$
Si un conjunto $latex \\displaystyle{ A=\\{1,2,3\\} }$ y un conjunto $latex \\displaystyle{ B=\\{1,2,3,4,5,6\\}}$, se dice que A pertenece a B y se escribe como $latex \\displaystyle{ A \\subseteq B}$, ya que el Conjunto B contiene a los elementos de A.
Operaciones con Conjuntos
Unión $latex \\displaystyle{ \\cup }$ : Ejemplo práctico $latex \\displaystyle{ A = \\{1,2,3\\} }$ y $latex \\displaystyle{ B = \\{4,5,6\\} }$, $latex \\displaystyle{ A \\cup B = \\{1,2,3,4,5,6\\}}$
Intersección $latex \\displaystyle{ \\cap }$ : Ejemplo práctico $latex \\displaystyle{ A = \\{1,2,3,4,5\\} }$ y $latex \\displaystyle{ B = \\{4,5,6,7,8\\} }$, $latex \\displaystyle{ A \\cap B = \\{4,5\\}}$
Diferencia $latex \\displaystyle{ - }$ : Otro Ejemplo $latex \\displaystyle{ A = \\{1,2,3,4,5\\} }$ y $latex \\displaystyle{ B = \\{4,5,6,7,8\\} }$, $latex \\displaystyle{ B - A = \\{6,7,8\\}}$
Producto cartesiano $latex \\displaystyle{ * }$ : Ejemplo $latex \\displaystyle{ A = \\{a,b,c\\} }$ y $latex \\displaystyle{ B = \\{e,f\\} }$, $latex \\displaystyle{ A * B = \\{(a,e),(b,e),(c,e),(a,f),(b,f),(c,f)\\}}$
Existen otras operaciones, y por el momento solo mencionare estas.
Cuantificadores
Cuantificador Universal $latex \\displaystyle{ \\forall }$ : Su uso recide en establecer que todos los elementos de un conjunto cumplen con cierta propiedad .
Cuantificador Existencal $latex \\displaystyle{ \\exists }$ : Su uso recide en establecer que almenos un elemento de un conjunto cumple con cierta propiedad.
Cadenas y Lenguajes
Al hablar de lenguajes en la teoría de la computación, necesitamos nombrar a los símbolos a utilizar en ese lenguaje, por ejemplo, los simbolos utilizados en un lenguaje que esta constituido por números, por letras, por jeroglíficos, etc. A este conjunto de símbolos los representaremos por el símbolo $latex \\displaystyle{ \\Sigma }$, y aquellas combinaciones que este conjunto pueda realizar, las llamaremos cadenas.
Por ejemplo, $latex \\displaystyle{ \\Sigma = {a,b,c} }$, una cadena que nuestro alfabeto $latex \\displaystyle{ \\Sigma }$ generaría sería $latex \\displaystyle{ abc }$, o tal vez $latex \\displaystyle{ acb }, o bien $latex \\displaystyle{ bca }$, en fin, también pueden ser grandes cadenas como $latex \\displaystyle{ abbbccc }$. Entonces podemos definir a una cadena como a una secuencia de símbolos de un alfabeto. Y un lenguaje como al conjunto de cadenas que genera un alfabeto.
Dentro del concepto "lenguaje" existe el denominado "lenguaje vacio" que esta formado por cero cadenas y lo denotamos por $latex \\displaystyle{ 0 }$
Concatenación: no es mas que la union de dos o mas cadenas, de tal forma que si $latex \\displaystyle{ a = flor }$ y $latex \\displaystyle{ b = marchita }$, la concatenación de estas dos cadenas será $latex \\displaystyle{ ab = flormarchita }$
Wikipedia [Teoría de Conjuntos]
Bibliografía:
Ramón Brena :: Automatas y Lenguajes
Wikipedia
Mis apuntes :: Jorge Luis Hernández C.
Jorge Hernandez :: http://jorgeluis.com.mx
