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 sea caracterí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 el conjunto 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 los elementos 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 el conjunto 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 conjunto no 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 cualquier alfabeto.

2.4 PROPIEDADES DE LAS CADENAS O “STRINGS”.

Una cadena (ó palabra) es una secuencia finita de símbolos. Por ejemplo: a, b y c son símbolos y abcb es una cadena.

2.4.1. Cadena Vacía.

La cadena vacía, denotada por  es la cadena que consiste en cero símbolos. Por tanto, tiene longitud ||=0.

2.4.2. Longitud.

Si w es una cadena sobre cualquier alfabeto, su longitud se denota como |w |. La longitud de w es el número de símbolos que tiene la cadena. Por ejemplo: abcb tiene longitud |w | =4.

2.4.3. Concatenación.

La concatenación de dos cadenas es la cadena que se forma al escribir la primera seguida de la segunda, sin que haya espacio entre ellas. Por ejemplo: si w= “banana” y z= “rama”, la concatenación de w con z es la cadena “bananarama”.

La concatenación de las cadenas w y z se denota como wz ó w.z. La cadena vacía es la identidad para el operador de concatenación. Es decir, w= w=w para cada cadena w.

2.4.4. Potencia de Cadenas.

La noción de potencia de una cadena sobre un alfabeto es dada por la notación wk que denota la concatenación de k copias de la cadena w.

Por tanto, si w=122 sobre el alfabeto ={1, 2}, se tiene

w0 = 

w1 = 122

w2 = 122122

w3 = 122122122

2.4.5.

...