Teoría de Conjuntos
Conjunto: Es una agrupación o colección de elementos u objetos.
Inclusión: Es cuando existe un vínculo entre dos o más conjunto.
Subconjuntos: Cuando un conjuntos posee los elementos de otro conjunto.
Inclusión propia: Un subconjunto pertenece a un conjunto pero es diferente a otros dentro del mismo conjunto.
Subconjunto propio: Los subconjuntos pertenecen a un conjunto que posee diferentes elementos.
Pertenencia: Un elemento forma parte de un conjunto.
Mapa Conceptual de Teoría de Conjuntos.
Teoría de Grafos.
¿Qué es un grafo?
De manera natural lo podemos definir de la siguiente manera: es un conjunto de vértices V con un conjunto de aristas E, de tal manera que cada arista de asocia a un par de vértices.
¿De qué formas serán los elementos V? y ¿De qué forma serán los elementos E?
V = {S,N,C,E}
E = {(N,E),(N,C),(C,N),(C,S),(S,C),(S,E),(C,E)}
Definición formal de un grafo.
Un grafo G es una dupla G = (V,E), donde V es un conjunto finito de vértices o nodos y E es un conjunto de pares no necesariamente ordenados de vértices por (x,y), que se denominan lados, aristas, etc.
Mapa conceptual de Teoría de Grafos.
Lenguaje Formal.
Símbolo: Es una representación distinguible de cualquier información. Los símbolos pueden ser cualesquiera, como w, 9, @
Alfabeto: Conjunto finito y no vacío de símbolos.
Alfabeto: Conjunto finito y no vacío de símbolos.
Palabra: Secuencia de símbolos de un alfabeto.
Longitud de una Palabra: Es la cantidad de símbolos que contiene, contando las repeticiones. La definición no restringe el número de símbolos que puede tener una palabra.
Una palabra puede estar conformada por una secuencia infinita de símbolos. Incluso puede carecer de ellas y se conoce como palabra vacía.
Lenguaje: Es simplemente un conjunto de palabras que están asociadas a un alfabeto.
Concatenación de Lenguaje: Para calcularlo hay que concatenar cada palabra del primero de ellos con cada una del segundo.
Cuando hablamos de computación, en realidad nos estamos refiriendo de manera directa a procesa información. La capacidad de procesar información, no podría existir sin la capacidad de comunicación; en este sentido, no podríamos comunicarnos si no usáramos un lenguaje adecuado, que permitiera el flujo de información ente los sujetos.
Cualquier secuencia de símbolos de un alfabeto puede ser considerada una palabra. Cuando escribimos una o varias palabras o caracteres uno a continuación de otro, se supone que forma una sola palabra (se concatenan). La notación usada para denotar la concatenación de dos palabras a y B es aB.
Clausula de Kleene.
Si L es un lenguaje, la clausula de Kleene para L, que notaremos por L*, es el conjunto más pequeño que contiene.
- La palabra vacía λ
- El conjunto L
- Todas las palabras formadas por la concatenación de miembros de L*
La definición de la clausula de Kleene es recursiva, pues en la tercera regla estamos suponiendo que ya hay palabras en L*
Preguntas y respuestas.
¿Un alfabeto puede contener infinidad de símbolos?
No, un alfabeto es un conjunto finito y no vacío de símbolos, ya que los símbolos son caracteres con un significado, no puede ser vacío.
¿Un lenguaje puede contener infinitas palabras?
Si, si tomamos en cuenta la concatenación de palabras podemos tener infinidad de palabras, si también tomamos que las palabras pueden tener infinidad de símbolos.
¿Una palabra puede carecer de símbolos?
Si, la definición de palabra no restringe el número de símbolos que debe tener una palabra. Entonces podemos denotar que una palabra puede carecer de símbolos.
¿Una palabra puede ser de longitud infinita?
Si, la definición de palabra no dice la longitud que ésta debe contener, si ponemos símbolos de un alfabeto uno después de otro estamos formando una palabra, aún si sus símbolos son infinitos para formar esa palabra.
Ejemplo de Concatenación.
Ejemplo 1:
Sean L1 y L2 dos lenguajes cualesquiera.
a. Calcular la unión de L1 y L2
La unión esta formado por todas las palabras que se encuentran en al menos uno de los dos lenguajes.
Sean L1 = {a,b,c,d} y L2 = {a,0,1,2}
L1 ∪ L2 = {a,b,c,d,0,1,2}
b. Calcular la intersección
La intersección esta formado por todas las cadenas que se encuentran en ambos conjuntos.
Ejemplo 2:
Sean L1 = {a,b,c,d} y L2 = {a,0,1,2}
L1 ∩ L2 = {a}
Sean los lenguajes L1 = {w|w es un nombre} 7 L2 = {w|w es un apellido}. Calcular la concatenación de L1 y L2.
Sean L1 = {carlos, enrique} y L2 = {ramos, meza}
L* = {carlosramos, carlosmeza, enriqueramos, enriquemeza}
Ejemplo 3:
Sea Σ = {0,1} un alfabeto. Determina la Clausula de Kleene para el alfabeto.
L* = {λ, 0, 1, 01, 10, 00, 11}
Gramática Formal.
Σn = Alfabeto inicial
Σt = Alfabeto terminal
S = Axioma
P = Producciones
Σn = {A, B}
Σt = {0, 1}
S = A
P = {
A → 0
A → B
B → 1
A → 0A
B → 1B
}
Para el lenguaje L = 001 tenemos las siguientes producciones hasta llegar a un estado terminal.
A → 0A
A → 00A
A → 00B
A → 001
Ejemplos:
Ejemplo 1:
Crear una gramática que genere el lenguaje L = {1, 11, 111, 1111,......}
Σn = {A}
Σt = {1}
S = A
P = {
A → 1A
A → 1
}
Ejemplo 2:
Crear una gramática que genere el lenguaje L = {0110, 100110, 01011010,.....}
Σn = {A, B}
Σt = {01, 10}
S = A
P = {
A → 01
A → B
B → 10
A → 01A
B → B10
A → 01B
}
Tipos de Lenguajes.
Regulares: Sus producciones solo puede ser de la forma A → a, A → aB, a → λ
Libres de Contexto: Sus producciones solo puede ser de la forma A → a, A → aBb, A → λ
Sensibles al Contexto: Sus producciones solo pueden ser de la forma ABc → aBb
Sin restricciones: Sin restricciones.
Desarrollo de proyecto de Grafos.
Archivos del proyecto desarrollado.
