Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 299 vistas

    Ejercicios Expresiones Regulares

    Cargado por

    realvaradog4831
    Este documento introduce las expresiones regulares, que representan lenguajes regulares de forma concisa. Define las expresiones regulares básicas y las operaciones de concatenación, unión y clausura de Kleene. Proporciona ejemplos de expresiones regulares para diferentes lenguajes y ejercicios para encontrar expresiones regulares de lenguajes específicos.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd

    Ejercicios Expresiones Regulares

    Cargado por

    realvaradog4831
    299 vistas3 páginas
    Este documento introduce las expresiones regulares, que representan lenguajes regulares de forma concisa. Define las expresiones regulares básicas y las operaciones de concatenación, unión y clausura de Kleene. Proporciona ejemplos de expresiones regulares para diferentes lenguajes y ejercicios para encontrar expresiones regulares de lenguajes específicos.

    Descripción original:

    Ejercicios Expresiones Regulares

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento introduce las expresiones regulares, que representan lenguajes regulares de forma concisa. Define las expresiones regulares básicas y las operaciones de concatenación, unión y clausura de Kleene. Proporciona ejemplos de expresiones regulares para diferentes lenguajes y ejercicios para encontrar expresiones regulares de lenguajes específicos.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    299 vistas3 páginas

    Ejercicios Expresiones Regulares

    Cargado por

    realvaradog4831
    Este documento introduce las expresiones regulares, que representan lenguajes regulares de forma concisa. Define las expresiones regulares básicas y las operaciones de concatenación, unión y clausura de Kleene. Proporciona ejemplos de expresiones regulares para diferentes lenguajes y ejercicios para encontrar expresiones regulares de lenguajes específicos.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 3

    1.14.

    Expresiones regulares

    Las expresiones regulares representan lenguajes regulares y su prop osito es simplicar la escritura de los lenguajes regulares. La siguiente es la denici on recursiva de las expresiones regulares sobre un alfabeto dado. 1. Expresiones regulares b asicas: es una expresi on regular que representa al lenguaje . es una expresi on regular que representa al lenguaje {}. a es una expresi on regular que representa al lenguaje {a}, a . 2. Si R y S son expresiones regulares sobre , tambi en lo son: RS RS R RS representa la concatenaci on de los lenguajes representados por R y S ; R S representa su uni on, y R representa la clausura de Kleene del lenguaje representado por R.

    Ejemplo

    Dado el alfabeto = {a, b, c}, (a b )a (bc)

    es una expresi on regular que representa al lenguaje ({a} {b} ) {a} {bc} .

    Ejemplo

    Dado el alfabeto = {a, b}, ( a) (a b) (ba)

    es una expresi on regular que representa al lenguaje ({} {a}) {a, b} {ba} .

    Ejemplos

    los con expresiones regulares:

    Los tres primeros lenguajes de la secci on 1.13 podemos representar-

    1. El lenguaje A de todas las palabras que tienen exactamente una a: A = b ab . 2. El lenguaje B de todas las palabras que comienzan con b: B = b(a b) . 3. El lenguaje C de todas las palabras que contienen la cadena ba: C = (a b) ba(a b) . Observaci on: La representaci on 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)

    (a b )

    representan el mismo lenguaje por la igualdad (1.1) de la secci on 1.11. Ejemplos


    guajes, denidos sobre el alfabeto = {a, b}.

    Encontrar expresiones regulares que representen los siguientes len-

    1. Lenguaje de todas las palabras que comienzan con b y terminan con a. Soluci on: b(a b) a. 2. Lenguaje de todas las palabras que tienen exactamente dos as. Soluci on: b ab ab . 3. Lenguaje de todas las palabras que tienen un n umero par de s mbolos (palabras de longitud par). Soluci on: (aa ab ba bb) . 4. Lenguaje de todas las palabras que tienen un n umero impar de s mbolos (palabras de longitud impar). Soluci on: a(aa ab ba bb) b(aa ab ba bb) . 5. Lenguaje de todas las palabras que tienen un n umero par de a s. Soluciones: b (ab a) b . (ab a b) . (b ab ab ) b . b (b ab ab ) b .

    on regular que represente el lenguaje de todas Ejemplo Encontrar una expresi las palabras que no contienen la cadena bc, denido sobre el alfabeto = {a, b, c}. Soluci on: c (b ac ) .

    Ejercicio

    Encontrar expresiones regulares para los siguientes lenguajes:

    1. = {a, b}. Lenguaje de todas las palabras que tienen la cadena ab un n umero par de veces. 2. = {a, b}. Lenguaje de todas las palabras que tienen un n umero impar de as. 3. = {a, b}. Lenguaje de todas las palabras que tienen un n umero par de as o un n umero impar de bs. 4. = {a, b, c}. Lenguaje de todas las palabras que tienen un n umero par de s mbolos. 5. = {a, b, c}. Lenguaje de todas las palabras que tienen un n umero impar de s mbolos. 6. = {a, b, c}. Lenguaje de todas las palabras que comienzan con c y terminan con b. 7. = {a, b, c}. Lenguaje de todas las palabras que no contienen la cadena cc. 8. (Opcional, Dif cil!) = {a, b}. Lenguaje de todas las palabras que tienen un n umero par de as y un n umero impar de bs. Observaci on: No todos los lenguajes sobre un alfabeto dado son regulares. M as adelante se mostrar a que el lenguaje L = {, ab, aabb, aaabbb, . . . } = {an bn : n 0} sobre = {a, b} no se puede representar por medio de una expresi on regular, y por lo tanto, no es un lenguaje regular.

    También podría gustarte