Autómatas: Lenguajes

Informática. Relaciones. Palabras. Alfabetos. Funciones Algorítmicas

  • Enviado por: M_bravo
  • Idioma: castellano
  • País: España España
  • 13 páginas

publicidad
cursos destacados
Programación Android 02 Lo necesario para empezar
Programación Android 02 Lo necesario para empezar
Tutoriales para descargar e instalar en tu ordenador lo necesario para empezar a escribir aplicaciones para...
Ver más información

Apps en HTML5 para BlackBerry 10
Apps en HTML5 para BlackBerry 10
Este curso te guiará en el desarrollo de una app completa para BlackBerry 10, paso a paso. La app que desarrollaremos...
Ver más información


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