Ingeniero Técnico en Informática de Sistemas


Autómatas: Lenguajes


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




    Descargar
    Enviado por:M_bravo
    Idioma: castellano
    País: España

    Te va a interesar