Fundamentos De Automatas Y Maquina De Turing

UNIDAD 3

Principios fundamentales de autómatas y Maquina de Turing

INTRODUCCIÓN

2.1 CONJUNTOS.

Un conjunto es una colección de objetos llamados elementos del conjunto. Si A es un conjunto y a es un elemento 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 lo tanto 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 seacaracterística de todos los elementos del conjunto.

Sea P(x) una proposición sobre x. La notación {x| P(x)}, se interpreta como “el conjunto de todas las x tales que P(x)”, denota el conjunto de todas las x para las cuales P(x) es una proposición verdadera. (Todas las x tienen la propiedad P).
2.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 en A, 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 elconjunto 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 son dos 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 loselementos 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 elconjunto 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 son conjuntos 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 ejemplo si 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 conjunto universal. Si A es un conjunto, entonces U-A es el conjunto de todos los elementos que no están en A.

2.3 ALFABETOS.

Un alfabeto es un conjuntono 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 se usan para construir palabras en inglés (tales como el guión, el apóstrofe y otros por el estilo).

Cada símbolo de un alfabeto es una cadena sobre dicho alfabeto. La cadena vacía, la cual se denota por el símbolo , es una palabra sobre...