2. Expresiones y Definiciones Regulares

  • Published on
    20-Oct-2015

  • View
    9

  • Download
    1

Embed Size (px)

Transcript

  • 2. LENGUAJES REGULARES Y EXPRESIONES REGULARES Tal como se haba expresado anteriormente, un lenguaje es un conjunto finito o

    infinito de cadenas, construidos a partir de los smbolos de un alfabeto. Para

    mayor comprensin de tal definicin, en este acpite se aborda una clasificacin

    de los mismos, en lenguajes regulares y lenguajes no regulares, comprobables

    mediante el lema del bombeo, temas que se describen en detalle a continuacin.

    2.1 CLASIFICACIN DE LOS LENGUAJES

    Figura No 1. Tipos de Lenguajes

    2.2 LENGUAJES REGULARES

    TIPOS DE LENGUAJES

    Lenguajes regulares

    Lenguajes no regulares

    Expresiones regulares

    Gramtica Independiente del

    contexto

    Se especifica mediante

    Se especifica mediante

  • Es un lenguaje que se forma a partir de los lenguajes bsicos como { } y {a}

    donde a y debe cumplir tres operaciones bsicas: Unin, concatenacin y

    cerradura de Kleene.

    2.2.1. Definicin Formal

    { } es un lenguaje regular.

    Si a pertenece al alfabeto ( ) entonces {a} es un lenguaje regular.

    Si L1 y L2 son lenguajes entonces L1 L2, L1 U L2, L1*, L2* son lenguajes

    regulares.

    2.2.2. Lema de Bombeo

    Los lenguajes regulares poseen una propiedad muy importante que permite

    demostrar que ciertos lenguajes no son regulares. Este lema es una herramienta

    til para ello. Tal vez no sea fundamental, pero al menos es un inicio.

    El lema de bombeo es una herramienta utilizada para demostrar que ciertos

    lenguajes aparentemente regulares no lo son, por medio de una estrategia

    conocida como reduccin al absurdo. Dicha estrategia consiste en partir de una

    suposicin aparentemente cierta, demostrar que es falsa por medio de pasos, los

    cuales poco a poco contradicen la veracidad de dicha suposicin.

    Lema de bombeo1: para todo lenguaje regular L (sobre un alfabeto dado ) existe

    una constante n N, llamada constante de bombeo para L, tal que toda cadena w

    L, con |w|>n, satisface la siguiente propiedad:

    1 D.K. Rodrigo. Teora de la Computacin: Lenguajes, Autmatas y Gramticas. Colombia: Unilibros, 2004. pp. 63-66.

  • P1: w se puede descomponer como w=xyz, con |xy| 0 se

    tiene xykz L

    Las restricciones bajo las cuales trabaja el lema de bombeo son las siguientes:

    Para todo lenguaje regular infinito L, existe una constante n, dependiente de ese

    lenguaje, de forma que si w es una cadena de L con |w| n, podemos partir w en

    tres cadenas, x, y, z, de forma que:

    w = xyz,

    y (o dicho de otro modo, que |y| 1),

    |xy|

  • - y

    - |xy|

  • Pero como j 1 tenemos que xy2

    z = a2n+j

    bn

    , es una palabra que no pertenece al

    lenguaje porque tiene ms del doble de aes que de bs (al menos una a ms).

    Hemos llegado por tanto a una contradiccin (una palabra que no es bombeable

    de ninguna forma para al menos una constante k en un lenguaje supuestamente

    regular) que viene de suponer precisamente que el lenguaje L es regular, luego L

    no es regular.

    Ejemplo: Usar el lema de bombeo para demostrar que el lenguaje L = {0i1i: i > 0}

    no es regular.

    Solucin. Supeniendo que L es regular, y adems n es un a constante bombeo.

    Sea w = 0n1n L. Entonces w se puede descomponer como w = uvx, con |v| > 1 y

    |uv| < n. Por lo tanto, u y v constan nicamente de a es:

    u = 0r, para algn r > 0,

    v = 1s, para algn s > 1.

    Entonces,

    x = 0n(r+s)1n = 0nrs 1n

    Por el lema de bombeo, uvix L para todo i > 0. En particular, si i = 0, ux L.

    Pero ux=0r1nrs1n=0ns1n. Como ns n, la cadena ux L lo cual es una

    contradiccin. Se concluye entonces que L no puede ser regular.

    Tomando i = 2 tambin se llega a una contradiccin: por un lado, uv2x L, pero

    uv2x = arasaSanrsbn = ar+2s+nrsbn= an+sbn

    Como s > 1, an+sbn no est en L.

  • El argumento anterior tambin sirve para demostrar que el lenguaje L = {aibi : i > 1}

    no es regular.

    2.2.3. Propiedades de las cerraduras

    Las propiedades de las cerraduras tiene gran importancia en la conformacin de

    otros lenguajes regulares, ya que a travs de estas propiedades se pueden

    mantener las caractersticas de regularidad de los lenguajes, por esta razn es

    que se concluye que todos los lenguajes regulares son cerrados bajos estas

    operaciones.

    Teorema. Si L1 y L2 son lenguajes regulares, entonces tambin son lenguajes

    regulares:

    # Operacin Descripcin

    (1) L1UL2 Unin

    (2) L1L2 Concatenacin

    (3) L1* o L1* Cerradura de Kleene

    (4) L1+ o L2

    + L1 = * L1

    Cerradura positiva

    (5) Complemento

    (6) L1L2 Interseccin (7) L1 L2 Diferencia (8) L1 L2 Diferencia Simtrica

    Tabla No 1. Propiedades de las Cerraduras

    Las demostraciones de estas propiedades se dejan como trabajo complementario

    del lector. Consideramos que estas demostraciones no son relevantes para los

    objetivos de este libro.

    Un lenguaje regular puede ser finito o infinito. De acuerdo a las propiedades de las cerraduras la unin de lenguajes regulares finitos tambin es regular, sin embargo la unin de lenguajes regulares infinitos no necesariamente regular.

    Por ejemplo,

  • 1

    1/

    i

    iinn banbaL

    NO es un lenguaje regular, lo cual se puede demostrar por el lema de Bombeo.

    Tambin se puede decir que los lenguajes contenidos dentro de un lenguaje

    regular no necesariamente son regulares, tambin se puede concluir que un

    lenguaje regular puede contener sublenguajes no-regulares, as:

    Si 1/ nba nnL

    Es un sublenguaje del lenguaje regular a*b* pero L nos regular.

    Las propiedades de cerradura permiten concluir, razonando por contradiccin, que

    ciertos lenguajes no son regulares. Esto se ilustra en los siguientes ejemplos en

    los que se usa el hecho de que los lenguajes L = {aibi: i > 0} y L = { aibi: i > 1} no

    son regulares.

    Ejemplo:

    L = {aibj: i, j > 0, ij} no es regular.

    Si lo fuera, a*b* L tambin lo sera, pero

    a*b* L = {aibi: i > 0}

  • 2.2.4. Homomorfismo

    En un mbito general, el homomorfismo, a veces llamado tambin morfismo, se

    define como una funcin que es compatible con toda la estructura relevante. Una

    nocin ms general de morfismo se estudia abstractamente en la teora de las

    categoras, la cual trata de forma abstracta con las estructuras matemticas y sus

    relaciones. Por ejemplo, si un objeto consiste en un conjunto X con un orden

    menor y el otro objeto consiste en un conjunto Y con orden mayor, entonces debe

    valer para la funcin que, si u < v f(u) < f(v).

    O, si en estos conjuntos hay definidas operaciones binarias + y *,

    respectivamente, entonces debe valer que: f(u + v) = f(u) * f(v). Ejemplos de

    morfismo son los homomorfismos de grupos, los homomorfismos de anillo, los

    operadores lineales y las funciones continuas, entre otras.

    En el contexto de los lenguajes regulares, el homomorfismo se define como una

    funcin que trabaja sobre cadenas, esto quiere decir que a cada smbolo que

    pertenece a una cadena se le asocia otra cadena por medio de la concatenacin.

    Ejemplo:

    Sea h: {0, 1}* {a, b}

    * definido como h (0) = ab, y h(1) = .

    Entonces h (0011) = abab y h (L (10* 1)) = L ((ab)*).

    En las temticas anteriores se ha definido el proceso para identificar si un lenguaje

    es o no regular, una vez comprendido este proceso se puede determinar que una

    de las formas de especificar un lenguaje regular, es mediante expresiones

    regulares, tema que se abordar en detalle a continuacin.

  • 2.3 EXPRESIONES REGULARES

    Las Expresiones Regulares simplifican la especificacin de un lenguaje regular y

    sirven para efectuar representaciones de los patrones.

    Los operadores que se utilizan en las expresiones regulares son los siguientes:

    Operador Descripcin

    . Concatenacin

    | Unin

    * Cerradura de Klenne

    + Cerradura Positiva

    ? Cerradura 0 o 1 caso

    (,) Agrupar

    Tabla No 2. Operadores usados en las Expresiones Regulares

    # Operador Descripcin

    1. ( , ) Parntesis

    2. *, + ,? Cerraduras

    3. . Concatenacin

    4. | Unin (se lee o y representa la unin en los lenguajes regulares).

    Tabla No 3. Orden Jerrquico de Evaluacin de los Operadores

    2.3.1. Definicin formal de Expresin Regular 1. es una expresin regular.

    2. si a pertenece a , entonces a es una expresin regular. 3. Si r y s son expresiones regulares, entonces su lenguaje regular es

    respectivamente L(r) y L(s).

    a. r es una expresin regular y se representa L (r) = {r}

  • b. (r | s) es una expresin regular y se representa,

    L(r) U L(s) = {r} U {s} = {r, s}.

    c. r . s es una expresin regular y se representa

    L(r) L(s) = {r}{s} = {rs}.

    d. r* es una expresin regular y se representa

    L*(r) = {r}* = { , r , r , rrr, rrrr}.

    2.3.2. Propiedades de las expresiones regulares

    Sean r, s y t expresiones regulares, a partir de las cuales se definen las siguientes

    propiedades:

    1 r. = .r = r

    2. r | = | r

    3. r | r = r

    4 (r . s) . t = r. (s . t)

    5 (r | s) | t =r | (s | t)

    6. r . (s | t) = r. s | r . t

    7. (r | s)t = r. t | s . t