Teaching Methods & Materials > Mathematics">
Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 152 vistas

    Expresiones Regulares

    Cargado por

    Carlos
    1. El documento describe las expresiones regulares, que representan lenguajes regulares de forma simplificada. Las expresiones regulares se construyen recursivamente a partir de símbolos individuales, concatenación, unión y clausura de Kleene. 2. Se proveen ejemplos de expresiones regulares y los lenguajes que representan sobre diferentes alfabetos. 3. Se plantean ejercicios para encontrar expresiones regulares que representen lenguajes descritos sobre diferentes alfabetos.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Expresiones Regulares

    Cargado por

    Carlos
    152 vistas5 páginas
    1. El documento describe las expresiones regulares, que representan lenguajes regulares de forma simplificada. Las expresiones regulares se construyen recursivamente a partir de símbolos individuales, concatenación, unión y clausura de Kleene. 2. Se proveen ejemplos de expresiones regulares y los lenguajes que representan sobre diferentes alfabetos. 3. Se plantean ejercicios para encontrar expresiones regulares que representen lenguajes descritos sobre diferentes alfabetos.

    Descripción original:

    AFD problemas resueltos

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    1. El documento describe las expresiones regulares, que representan lenguajes regulares de forma simplificada. Las expresiones regulares se construyen recursivamente a partir de símbolos individuales, concatenación, unión y clausura de Kleene. 2. Se proveen ejemplos de expresiones regulares y los lenguajes que representan sobre diferentes alfabetos. 3. Se plantean ejercicios para encontrar expresiones regulares que representen lenguajes descritos sobre diferentes alfabetos.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    152 vistas5 páginas

    Expresiones Regulares

    Cargado por

    Carlos
    1. El documento describe las expresiones regulares, que representan lenguajes regulares de forma simplificada. Las expresiones regulares se construyen recursivamente a partir de símbolos individuales, concatenación, unión y clausura de Kleene. 2. Se proveen ejemplos de expresiones regulares y los lenguajes que representan sobre diferentes alfabetos. 3. Se plantean ejercicios para encontrar expresiones regulares que representen lenguajes descritos sobre diferentes alfabetos.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 5

    1.14.

    Expresiones regulares

    Las expresiones regulares representan lenguajes regulares y su proposito es simplificar la escritura de los lenguajes regulares.
    La siguiente es la definicion recursiva de las expresiones regulares sobre un
    alfabeto dado.
    1. Expresiones regulares basicas:
    es una expresion regular que representa al lenguaje .
    es una expresion regular que representa al lenguaje {}.
    a es una expresion regular que representa al lenguaje {a}, a .
    2. Si R y S son expresiones regulares sobre , tambien lo son:
    (R)(S)
    (R S)
    (R)
    (R)(S) representa la concatenacion de los lenguajes representados por R y
    S; (R S) representa su union, y (R) representa la clausura de Kleene del
    lenguaje representado por R. Los parentesis ( y ) son smbolos de agrupacion
    y se pueden omitir si no hay peligro de ambig
    uedad.
    Para una expresion regular R cualquiera se utiliza en ocasiones la siguiente notacion:
    L(R) := lenguaje representado por R.
    Utilizando esta notacion y la definicion de expresion regular podemos escribir,
    para R y S expresiones regulares arbitrarias:
    L() = .
    L() = {}.
    L(a) = {a}, a .
    L(RS) = L(R)L(S).
    L(R S) = L(R) L(S).
    L(R ) = L(R) .
    

    Ejemplo

    Dado el alfabeto = {a, b, c},


    (a b )a (bc)

    es una expresion regular que representa al lenguaje


    ({a} {b} ) {a} {bc} .
    

    Ejemplo

    Dado el alfabeto = {a, b},


    ( a) (a b) (ba)

    es una expresion regular que representa al lenguaje


    ({} {a}) ({a} {b}) {ba} .
    

    tarlos con expresiones regulares:

    Ejemplos

    Los tres primeros lenguajes de la seccion 1.13, podemos represen-

    1. El lenguaje A de todas las cadenas que tienen exactamente una a:


    A = b ab .
    2. El lenguaje B de todas las cadenas que comienzan con b:
    B = b(a b) .
    3. El lenguaje C de todas las cadenas que contienen la cadena ba:
    C = (a b) ba(a b) .

    La representacion de lenguajes regulares por medio de expresiones regulares no es u


    nica. Es posible que haya varias expresiones regulares diferentes
    para el mismo lenguaje. Por ejemplo, b(a b) y b(b a) representan el
    mismo lenguaje.
    Otro ejemplo: las dos expresiones regulares (a b) y (a b ) representan
    el mismo lenguaje por la igualdad establecida en el ejercicio final de la
    seccion 1.11

    guajes, definidos sobre el alfabeto = {a, b}:

    Ejemplos

    Encontrar expresiones regulares que representen los siguientes len-

    1. Lenguaje de todas las cadenas que comienzan con b y terminan con a.


    Solucion: b(a b) a.

    2. Lenguaje de todas las cadenas que tienen un n


    umero par de smbolos (cadenas de longitud par).
    Solucion: (aa ab ba bb) .
    3. Lenguaje de todas las cadenas que tienen un n
    umero par de aes.
    Soluciones:
    b (b ab ab ) .
    (ab a b) .
    (b ab ab ) b .
    

    guajes, definidos sobre el alfabeto = {0, 1}.

    Ejemplos

    Encontrar expresiones regulares que representen los siguientes len-

    1. Lenguaje de todas las cadenas que tienen exactamente dos ceros.


    Solucion: 1 01 01 .
    2. Lenguaje de todas las cadenas cuyo pen
    ultimo smbolo, de izquierda a derecha, es un 0.
    Solucion: (0 1) 0(0 1).
    

    Ejemplo Sea = {a, b, c}. Encontrar una expresion regular que represente el
    
    lenguaje de todas las cadenas que no contienen la cadena bc.
    Solucion: Una b puede estar seguida solamente de otra b o de una a, mientras
    que las aes y las ces pueden estar seguidas de cualquier smbolo. Esto se puede
    visualizar por medio del siguiente diagrama:

    Teniendo en cuenta todas las restricciones y posibilidades, arribamos a la siguiente


    expresion: (a c b+ a) b . Una expresion regular mas sencilla para este lenguaje
    es c (b ac ) .

    tinuaci
    on:

    Ejercicios

    Encontrar expresiones regulares para los lenguajes descritos a con-

    1. = {0, 1, 2}. Lenguaje de todas las cadenas que comienzan con 2 y terminan con 1.
    2. = {a, b, c}. Lenguaje de todas las cadenas que tienen un n
    umero par de
    smbolos.
    3. = {a, b}. Lenguaje de todas las cadenas que tienen un n
    umero impar de
    smbolos.
    4. = {a, b, c}. Lenguaje de todas las cadenas que tienen un n
    umero impar
    de smbolos.
    5. = {a, b}. Lenguaje de todas las cadenas que tienen un n
    umero impar de
    aes.
    6. = {0, 1}. Lenguaje de todas las cadenas que tienen por lo menos un 0 y
    por lo menos un 1.
    7. = {0, 1}. Lenguaje de todas las cadenas que tienen a lo sumo dos ceros
    consecutivos.
    8. = {0, 1}. Lenguaje de todas las cadenas cuyo quinto smbolo, de izquierda
    a derecha, es un 1.
    9. = {0, 1}. Lenguaje de todas las cadenas de longitud par 2 formadas
    por ceros y unos alternados.
    10. = {0, 1}. Lenguaje de todas las cadenas cuya longitud es 4.
    11. = {0, 1}. Lenguaje de todas las cadenas de longitud impar que tienen
    unos u
    nicamente en las posiciones impares.
    12. = {a, b}. Lenguaje de todas las cadenas que tienen la cadena ab un
    n
    umero par de veces.
    13. = {a, b}. Lenguaje de todas las cadenas que tienen un n
    umero par de aes
    o un n
    umero impar de bes.
    14. = {0, 1}. Lenguaje de todas las cadenas cuya longitud es un m
    ultiplo de
    tres.

    15. = {0, 1, 2}. Lenguaje de todas las cadenas que no contienen dos unos
    consecutivos.
    No todos los lenguajes sobre un alfabeto dado son regulares. Mas
    adelante se mostrara que el lenguaje
    L = {, ab, aabb, aaabbb, . . . } = {an bn : n 0}
    sobre = {a, b} no se puede representar por medio de una expresion
    regular, y por lo tanto, no es un lenguaje regular.

    También podría gustarte