TEMA I: Teoría de Conjuntos

1.1 Conjuntos

Def: Un conjunto es una colección de objetos o elementos

Def: Sean A y B conjuntos. Se define f aplicación de A en B

f: A ! B

x ! f(x)

• f: A ! B es inyectiva si y sólo si x " y, x, y " A ! f(x) " f(y)

• f: A ! B es suprayectiva si y sólo si " y " B " x " A / y = f(x)

• f: A ! B es biyectiva si es inyectiva y suprayectiva.

Def: Se define cardinal de un conjunto øXø el número de elementos de X si X es finito.

Def: Se define el conjunto Partes de X como el conjunto formado por todos los subconjuntos de X.

Teorema: Si X es finito, øP(X)ø= 2øXø.

n=1 ! øXø=1; X={1}. P(X)={, {1}} ! øP(X)ø=2=21=2øXø.

øXø=n, supongo que øP(X)ø=2øXø. X={x1, x2, x3...xn}.

Sea Y={ x1, x2, x3...xn, y} con y " xi. øYø=n+1.

P(Y)=P(X) " (P(Y)\P(X)) ! øP(Y)ø= øP(X)ø+ øP(Y)\P(X)ø= 2øXø+øY2ø.

La aplicación de P(X) en Y2 es biyectiva, por tanto, øY2ø=øP(X)ø

! øP(Y)ø= 2øXø+2øXø= 2øXø+1=2øYø.

Corolario: " X conjunto finito, øP(X)ø>øXø

Def: Sean X, Y conjuntos. Se dice ø Xø<øYø si f: X ! Y es inyectiva.

Se dice ø Xø=øYø si f: X ! Y es biyectiva.

Teorema: Sean X, Y conjuntos. Si ø Xø<=øYø y ø Yø<=øXø ! ø Xø=øYø.

Teorema: Si X conjunto entonces ø Xø<øP(X)ø.

Corolario: No " cardinal máximo.

Axioma de Elección: Dada una colección de conjuntos no vacíos, existe una función g cuyo dominio es la colección de conjuntos de forma que " los conjuntos X de la colección la imagen de ese conjunto es un elemento de ese conjunto:

g / x " C, g(X) " X, dom(g) = C.

Teorema: øNø " øXø " X infinito.

Def: Un conjunto X es numerable si X es finito o si " f: X ! N inyectiva.

Un conjunto X no es numerable si no cumple ls anteriores.

1.2 Relaciones

Def: Se dice que existe Relación de A en B si (a, b) " A*B

Propiedades: Sea S conjunto y R relación en S. R es:

• Reflexiva si " a " S, aRa.

• Simétrica si aRb ! bRa.

• Transitiva si aRb " bRc ! aRc.

• Irreflexiva si " a " S, a¬Ra.

• Antisimétrica si aRb ! b¬Ra.

Sean A y B conjuntos y R relación binaria de A en B.

Dom(R) = {x "A / " y " B " (x, y) " R};

Im(R) = {y " B / " x " A " (x, y) " R}

R-1 = {(b, a) " B*A / (a, b) " R}

Partición de A:

Def: Una colección de subconjuntos no vacío A de A es una partición si y sólo si

• B, C " A ! (B = C) " (B " C = ).

Def: Sean A, B, C conjuntos y R " A*B y S " B*C.

Definimos R compuesta con S (SoR) como

SoR={(a, c) " A*C / " b " B (a, b) " R y (b, c) " S}

Relación de Equivalencia:

Def: R en A es de equivalencia si es reflexiva, transitiva y simétrica.

Teorema: Toda relación de equivalencia provoca una partición en el conjunto.

Teorema: Toda partición A de A induce una relación de equivalencia.

Def: Sea S conjunto y R de equivalencia en S. Al conjunto formado por todas las clases de equivalencia de R se denomina conjunto cociente de R en S: SøR.

Def: Sea P un conjunto de propiedades de relaciones de un conjunto.

Sea R una relación. Se llama P clausura de R a la menor relación que incluye todos los pares de R y cumple todas las propiedades de P. Lo notamos R+.

1.3 Funciones

Def: Una función de A en B es un conjunto de A x B en el que no existen pares con el mismo primer componente: Dom(f) = {x " A / " y " B ,, (x, y) " f}.

Teorema: Sean f y g funciones totales de A en B. f = g ! f(x) = g(x) " x " A.

Def: Sean A, B y C conjuntos y f y g funciones. Se define g o f como

g o f = {(a, c) " A x C / " b " B, b = f(a) " c = g(b)};

g o f = (a, g(f(a));

Cálculo 

Homomorfismos e isomorfismos:

Def: Sean f: A A y g: B B y sea t la aplicación t: A B (x u = t(x)) tal que g(t(x)) = t(f(x)). Se dice que f y g son homomorfas y t un homomorfismo. Si t es biyección, se dice que f y g son isomorfas y que t es un isomorfismo.

TEMA II: Alfabetos y Palabras

2.1 Alfabetos

Def: Alfabeto es el conjunto no vacío y finito de letras.

Def: Palabra es toda sucesión finita de letras.

Def: La longitud de una palabra respecto de un alfabeto øxø es el número de letras del alfabeto  que compone la palabra x.

Se llama palabra vacía  a aquella formada por  letras de . øø= .

Aplicación x ! x = {0, ..., m - 1} !  con øxø = m.

Def: m es el conjunto de todas las palabras X tal que øxø = m.

Universo de discurso *

, tiene la palabra ; , no la tiene, + = * \ {  }

corolarios: i)  " * " 

* es infinito " 

ø ø: * ! N donde øø = 0 y øaø = 1 + øø con a " , y  " *

Operaciones entre palabras

• Concatenación

Sean x e y palabras de un mismo alfabeto x, y " *. Se llama concatenación a colocar el segundo término después del primero:  = x . y

Propiedades:

i) Es aplicación: recoge palabras y devuelve como resultado una palabra, es pues una operación cerrada en el universo de discurso. * . * ! *

ii) Es asociativa: (x . y) . z = x . (y . z)

iii) Elem. Neutro: " U " * / x . u = u . x = x, u = .

PERO no es conmutativo. Concluimos que (*, .) es un semigrupo con elemento neutro, o monoide libre.

Ley: Todo monoide libre cumple la ley de “Cancelación por la izquierda”. Esta ley se cumple para todo monoide: a . b = a . c ! b = c

Ley: La ley de “Cancelación por la derecha” no se cumplirá para todos los monoides libres. b . a = c . a ! b = c

Sean x, y, z " * tal que z = x . y. x es prefijo propio de z si y " 

Y es sufijo propio de z si x " 

Observación: La función longitud es isomorfa a la función logaritmo, respecto de la concatenación. øx . yø = øxø + øyø, igual que log (x . y) = log x + log y.

Def:  sub-cadena o sub-palabra de z si " x, y " * / z = x .  . y

x " *, i " N, x[i] " i-ésima letra de x.

• Potencia de una letra

Sea a "  y n " N. Potencia n-ésima de a, an, se defina como:

a0 = 

a1 = a

ai+1 = a . ai con i " N

Teorema: Sea  un alfabeto ! * es numerable.

Como no es finito, hay que demostrar que " f: * ! N es inyectiva.

• Orden parcial

Definimos la relación "entre palabras como: (x, y " *)

x " y : ! " z " * / y = x . z

x " y : ! x " y " x " y

• Orden total o lexicográfico

Sean x, y " *,  = {a1 . . . an}

x "y ! x "y " " u, v, w " * " " i, j " N / x = u . ai . v, y = u . aj . w " i < j

• o bien x es prefijo de y

• o bien no es un prefijo, y empiezan a ser iguales y dejan de serlo.

Def: Sea x " *, x = x[1] . x[2] . . . x[k]

Se define la palabra inversa x-1 como: x-1 = x[k] . x[k-1] . . . x[2] . x[1]

øxø = øx-1ø

-1 = 

Funciones Algorítmicas

Sea  un alfabeto, a un algoritmo sobre  que admite un dato de entrada y devuelve un dato de salida:

Def: Sea  una función parcial n-ária (con n argumentos) sobre ,  es

algorítmica si " a algoritmo tal que .

Conjetura de Fermat: x, y. z " R; xn + yn = zn, con n > 2

Lenguajes

Def: Llamamos lenguaje sobre un alfabeto  a cualquier subconjunto del universo de discurso: L " *.

El conjunto vacío es un lenguaje sobre cualquier alfabeto.

El conjunto formado sólo por la palabra vacío es también lenguaje sobre cualquier alfabeto (" " {  } por que ø"ø = 0 y ø{  }ø = 1)

Operaciones entre lenguajes

Sean L1, L2, L3 lenguajes sobre un mismo alfabeto .

Unión

L1 " L2 = {x " * / (x " L1) " (x " L2)}

Es operación cerrada, la unión de lenguajes es un lenguaje.

Es asociativa: (L1 " L2) " L3 = L1 " (L2 " L3).

Tiene elemento neutro (el lenguaje vacío).

Es conmutativa: L1 " L2 = L2 " L1.

Es una proposición idempotente: L " L = L.

Concatenación de lenguajes

L = L1 . L2 = {z " L / " x " L1 " " y " L2 . . z = x . y}

Es cerrada, asociativa y elemento neutro: {  }.

Teorema: Sean A, B, C " *

A . (B " C) = (A . B) " (A . C)

(A " B) . C = (A . C) " (B . C)

Es por tanto distributiva por derecha y por izquierda.

Potencia de un lenguaje

Sea L " *. Definimos la potencia i-ésima de L como Li, resultado de concatenarse a si mismo i veces.

También definimos L1 como L y L0 como {  }.

Clausuras de un lenguaje

A la clausura de L la llamamos L* y está definida como la unión de todas las potencias de L (Cierre de Kleene): .

La clausura positiva, L+: .

Teorema: i) L* = L+ " {  }.

ii) L+ = L . L* = L* . L

Reflexión de L

L-1 = {x " * / x-1 " L}

Teorema: i) (L-1)-1 = L

ii) (A . B)-1 = A-1 . B-1

Operaciones con lenguajes sobre distintos alfabetos

• Homomorfismos

Def: f: A* ! B* es homomorfismo si f(  ) =  y si f(x, y) = f(x) . f(y)

TEMA III: Lenguajes Regulares y Autómatas Finitos

3.1 Lenguajes y expresiones regulares

• Analizador léxico

Diagrama de estados

Código

Estado := 1;

Repite

Leer siguiente símbolo de la palabra;

Case estado is

1 ! if símbolo = letra then estado := 3;

elsif símbolo = digito then estado := 2;

else rutine _ error;

2 ! rutine _ error;

3 ! if símbolo = letra then estado := 3;

elsif símbolo = digito then estado := 3;

else rutine _ error;

fin del case;

hasta fin de cadena;

if estado " 3 then rutine _ error;

Tabla de estados

	Letra	Dígito	Fin de cadena
1	3	2	Error
2	Error	Error	Error
3	3	3	Aceptar

• Lenguaje regular

Def: sea  alfabeto. El conjunto de lenguajes regulares se define como

" es lenguaje regular.

{} es lenguaje regular.

" a " , {a} es lenguaje regular.

si A y B son lenguaje regular ! A " B, A . B y A* son lenguajes regulares.

Ningún otro lenguaje es regular.

Ej.  = {a, b}

L1 = {a, ab, b} = {a} " {a} . {b} " {a} es lenguaje regular.

L2 = {ai / i " 0} = {} " {a} " ... " {a ... a} lenguaje regular.

L3 = {aibj / i " 0 " j " 0} = {ai / i " 0} . {bj / j " 0} es lenguaje regular.

• Expresión regular

Def:  alfabeto. El conjunto de lenguajes regulares se define como

" es expresión regular.

 es expresión regular.

a "  es expresión regular.

ð y ð son expresión regular ! ð ð ð, ð ð ð son expresión regular.

ð es expresión regular ! ð* es expresión regular.

Sólo son expresiones regulares las que se pueden formar aplicando las reglas anteriores un número finito de veces con las letras de , " y .

Dado ð expresión regular, decimos que L es lenguaje asociado, L(ð) si

ð = " ! L(ð) = "

ð = ð ! L(ð) = {ð}

ð = a ! L(ð) = {a}, a " 

ð ð ð ð γ ! L(ð) = L(ð) + L(γ)

ð ð ð ð γ ! L(ð) = L(ð) . L(γ)

ð ð ð* ! L(ð) = L(ð*) = L(ð)*

Def: Sean ð y ð expresión regular. Diremos que ð y ð son equivalentes si L(ð) = L(ð)

Teorema: L es regular ! " ð expresión regular / L = L(ð).

Propiedades:

+ es asociativa

+ es conmutativa

. es asociativa

. es distributiva con respecto de la suma

. tiene elemento neutro: ð ð ð ð ð ð ð ð ð

+ tiene elemento neutro: " ð ð ð ð ð " ð ð

ð* = ð

" ð ð ð ð ð " ð ð

"* = ð

ð* . ð* = ð*

ð* . ð = ð ð ð*

(ð*)* = ð*

ð* = ð ð ð ð ð2 + ... + ðn + ðn+1 . ð*

ð* = ð ð ð ð ð*

ð* = (ð ð ð)n-1 + ðn . ð*

(ð* + ð*)* = (ð* . ð*)* = (ð ð ð)*

(ð ð ð)*. ð = ð . (ð ð ð)*

(ð* ð ð)*. ð* = (ð ð ð)*

(ð ð ð)* = (ð ð ð)* . ð ð ð, (ð* ð ð)* = ð ð (ð ð ðð* + 

R = S* . T ! R = S . R + T

Si  " S ,, R = S . R + T! R = S* . T

3.2 Autómatas finitos

Es una máquina que recibe una entrada, la procesa y devuelve un valor booleano. Un autómata finito determinista es M = (ð, Q, δ, q0, F) con

: alfabeto de entrada

Q: conjunto de estados

δ: función de transición

q0: estado inicial

F: " Q, conjunto de estados finales

Teoría de Autómatas y Lenguajes Formales

Página 13

! (x, f(x)) " A * B ,, " x " A " ! y " B ,, y = f(x)

Y2={A"Y/y"A}

fct. longitud

1

2

3

dígito

letra

letra

dígito

Leyes de Inferencia