subconjuntos
Sean A y B dos conjuntos tal que cada elemento de A es también elemento de B. Entonces se diceque:
A es un subconjunto de B, y se denota A ⊆ B
Se lee como: Subconjunto de
A ⊆ B significa: cada elemento de A es también elemento de B
A ⊂ B significa: A ⊆ B pero A ≠ B
A ∩ B significa: elconjunto que contiene todos aquellos elementos que A y B tienen en común.
A ∩ B ⊆ A; Q ⊂ R
La idea de subconjunto es relativa a otro conjunto.
Se dice que A es subconjunto de E si todo elementode A pertenece a E.
Por ejemplo, el conjunto de A {animales mamíferos} es subconjunto del conjunto E {animales vertebrados}, pues todo animal de A pertenece a E. Podría decirse que A ⊆ E
En teoríade la computación, la Construcción de subconjuntos es un método estándar para, partiendo de un NFA (Autómata Finito No Determinista), obtener un DFA (Autómata Finito Determinista) equivalente, esdecir, que reconozca el mismo Lenguaje regular. En la teoría es importante porque establece que los NFAs aunque son más flexibles, no pueden reconocer ningún lenguaje que un DFA no pueda. Sin embargo, dadoun NFA con n estados, el DFA equivalente podría tener hasta 2^{n} estados, por lo que a veces, construir un DFA a partir de un NFA de gran tamaño no es practicable. Este problema se minimiza en granmedida con el algoritmo de Construcción de subconjuntos, el cual limita la inserción de estados al DFA resultante únicamente a los casos estrictamente necesarios.
Una vez que tenemos definido elestado de arranque de nuestro DFA, podemos empezar a completar los estados y transiciones restantes. Como sabemos que S representa un conjunto de estados del NFA inicial, sólo tenemos que hacer transitardicho conjunto con cada símbolo de nuestro alfabeto y estudiar a que otros conjuntos se llega. Si estos otros conjuntos no pertenecen a Q', entonces los añadiremos a nuestro DFA, en el caso...
Regístrate para leer el documento completo.