Manual Expresiones Regulares PDF

Preview

Summary

Apuntes de las clases, para examen de expresiones regulares...

Description

CURSO TEORIA DE LENGUAJES EJERCICIOS RESUELTOS EXPRESIONES REGULARES AUTOMATAS FINITOS

DOCENTE ING SANDRA RODRIGUES

TEORIA DE LENGUAJES UNC

2

EXPRESIONES REGULARES a) Unión alternativa { α | β } = { α } U { β } = (a | b)* =(a+b)* b) Concatenación α β={ α } { β } c) Cierre operación estrella { α *} = { λ , α , α α , α α α , α α α α … } d) Cierre positivo { α+ } = { α , α α , α α α , α α α α … } PROPIEDADES DE LAS EXPRESIONES REGULARES 1. α + (β + γ) = (α + β) + γ 2. α + β = β + α 3. α + Ø = α 4. α + α = α 5. α · λ = α 6. α · Ø = Ø 7. α · (β · γ) = (α · β) · γ 8. α · (β + γ) = αβ + αγ, (β + γ) · α = βα + γα 9. λ* = λ 1O. Ø* = λ 11. α · α* = α* · α= α* 12. α* = α* · α* = (α*)* = (α α*)* 13. α* = λ + α · α* 14. (α + β)* = (α* + β*)* 15. (α + β)* = (α* · β*)* = (α* · β)* · α* 16. α · (β · α)* = (α · β)* · α 17. Si λЄ L(a), entonces a+λ=a 18. ( λ |expresión regular)=(expresión regular)*

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

3

EJERCICIOS DE EXPRESIONES REGULARES EJERCICIO 1: Sea el vocabulario V = { a , b } y la expresión regular aa*bb*. Indicar el lenguaje que denota y algunas cadenas de dicho lenguaje. SOLUCION PROPIEDAD

α · α* = α* La Expresión regular es : aa*bb*=a*b* Algunas cadenas: ab, aab , aaaab , abbbb , abb. El lenguaje que se describe es L= {cadenas que comienzan por una a y continúan con varias o ninguna a, y siguen con una b y continúan con varias o ninguna b}. L= a+ b+ EJERCICIO 2: Sea el vocabulario V = {0,1} Hallar una expresión regular que denota el conjunto de cadenas que empiezan por uno y van seguidas por (01) cualquier número de veces o ninguna. SOLUCION

Las tiras son: 1 101 10101 1010101 101010101... La Expresión regular es: 1(0 | 1)* EJERCICIO 3: Dada la expresión regular (a | b)*, el lenguaje que denota es el que puede formar con todas las cadenas compuestas por a y b incluida la cadena vacía. Hallar algunas cadenas de la expresión regular (a | b)*

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

4

SOLUCION

Cadenas de la expresión regular (a | b)* λ aaa bbb aba abaaa abbaa EJERCICIO 4: Sea el vocabulario {1,2, 3 }, la expresión regular (1|2)*3 hallar el conjunto de todas las cadenas formada por los símbolos 1 y 2, sucediéndose cualquier Nº de veces (y en cualquier orden), y siempre terminando la cadena en el símbolo 3. SOLUCION

3 13 123 11113 22213 23 223 113 121211223 111212213

EJERCICIO 5: Hallar una Expresión regular para un lenguaje que tiene tiras a y bc SOLUCION

La Expresión regular de las tiras a y bc es: a│bc = { a , bc }

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

5

EJERCICIO 6: Hallar una Expresión regular que denota el lenguaje compuesto por todas las cadenas cuya longitud es cero o un número par y están compuestas solamente por el símbolo a , el símbolo b o por símbolos a y b SOLUCION

La tira a no se considera porque nos piden tiras pares, por eso no se considera la tira a Tiras que forman el lenguaje

λ aa bb ab ba aaba bbbb La Expresión regular es: ( (a│b) (a│b) )* EJERCICIO 7: Hallar las tiras de la Expresión regular (a│b│ab)* SOLUCION

a b ab abab aab bbbbbab TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

6

EJERCICIO 8: Hallar una Expresión regular, formadas por las cadenas de longitud 2, formadas con las cadenas a y b SOLUCION

Las tiras que forman el lenguaje son aa ab ba bb

La Expresión regular es:

(a│b)(a│b)

EJERCICIO 9: SOLUCION

Sea la Expresión regular t = a + bc + b3a Cuál es el lenguaje descrito por t Que expresión regular corresponde al lenguaje universal sobre el alfabeto {a, b, c} SOLUCION

En primer lugar, esta no es estrictamente hablando una Expresión regular, ya que no se permite b3a Sin embargo, aceptamos como válida la expresión a + bc + b3a, como una simplificación de la Expresión regular a + bc + bbba En ese caso, L (t) = {a; bc; bbba }, que como vemos es un lenguaje finito sobre el alfabeto {a; b; c}. La Expresión regular es : (a + b + c)* EJERCICIO 10: Simplificar la Expresión regular t = a + a (b + aa) (b*aa)* b* + a (aa + b)* SOLUCION

Aplicando las propiedades de las expresiones regulares, podemos obtener una Expresión regular equivalente con tan solo 4 operadores: a + a (b + aa) (b*aa)* b* +a (aa + b)*

(Propiedad 15)

a + a (b + aa) (b + aa)* +a (aa + b)*

(Propiedad 8)

a( λ + (b + aa) (b + aa)* ) + a (aa + b)*

(Propiedad 13)

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC a( b + aa )* + a (aa + b)*

(Propiedad 2)

a(aa + b)* + a (aa + b)*

(Propiedad 4)

7

a(aa + b)* EJERCICIO 11: Simplificar la Expresión regular 1*01*0 (01*01*0 + 1)* 01* + 1* de forma que sólo aparezca un operador + SOLUCION

1*01*0 (01*01*0 + 1)* 01* + 1*

(Propiedad 15)

1*01*0 (1* • 01*01*0)* 1* • 01* + 1*

(Propiedad 16)

(1*01*0 • 1*0)* 1*01*01*01* + 1* ((1*01*01*0)* 1*01*01*0 + λ) 1* (1* • 01*01*0)* 1*

(Propiedad 8) (Propiedad 13) (Propiedad 15)

(1 + 01*01*0)* EJERCICIO 12: Hallar una expresión regular que tiene un Lenguaje formado por las cadenas que terminan en 01 SOLUCION

{0,1}*. {01} ({0} U {1})*. {01} Expresión regular es : (0+1)*01 EJERCICIO 13: Encontrar una expresión regular que represente el lenguaje de todas las palabras que no contienen la cadena bc, definido sobre el alfabeto V= {a, b, c}. SOLUCION

Expresión regular es

:

c*(b │ ac*)* EJERCICIO 14: Hallar una expresión regular que represente Lenguaje formado por palabras de longitud par sobre a’s y b’s SOLUCION

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

8

{ aa , ab , ba , bb }* ( {aa} U {ab} U {ba} U {bb} )* Expresión regular es : (aa+ab+ba+bb)* EJERCICIO 15: Hallar una expresión regular que denote el lenguaje consistente de: al menos dos ceros precedidos por cualquier número de 0’s seguidos por cualquier número de 1’s. SOLUCION

Primero podemos desarrollar una Expresión regular para 0 y para 0 que denotan los lenguajes {0} y {0} respectivamente. Si concatenamos las dos expresiones 00, obtenemos el lenguaje {00}. Veamos ahora como construir el resto, cualquier número de 0’s lo podemos escribir como 0 y lo mismo para cualquier número de 1’s , 1 y ahora debemos describir la concatenación 0 1 La Expresión regular es: 0*1* 00

EJERCICIOS DE AUTOMATAS 1.Para los lenguajes dados sobre Te = {a, b} construir una expresión regular de él y un Autómata Finito que lo acepte: a) b) c) d) e) f)

L = { w|w tiene un numero par de a′s } L = { w|w tiene un numero impar de a′s } L = { w|w tiene un numero múltiplo de 3 de a′s } L = { w| toda a en w está entre dos b′s } L = { w| no hay dos a′s consecutivas en w } L = { w| w no contiene la subpalabra aa ni bb }

SOLUCION a) Una expresión regular que represente el lenguaje L es b∗(ab∗ab∗)∗ El diagrama de transición de un Autómata Finito es:

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

9

b) Una expresión regular para este lenguaje es: b∗ab∗(ab∗ab∗)∗. El diagrama de transición de un Autómata Finito es:

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

10

c) Una expresión regular para este lenguaje es: b∗(ab∗ab∗a)∗. El diagrama de transición de un Autómata Finito es:

d) Una expresión regular para este lenguaje es: b ∗ ∪ b+(ab+) ∗. El diagrama de transición de un Autómata Finito es:

e) Una expresión regular para este lenguaje es: b ∗(ab+)∗ ∪ b∗a(b+a) ∗. El diagrama de transición de un Autómata Finito es:

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

11

f) Una expresión regular para este lenguaje es: ǫ ∪ (b + ǫ)(ab) ∗ ∪ (a + ǫ)(ba) ∗. El diagrama de transición de un Autómata Finito es:

2.Para los lenguajes dados sobre Te= {a,b} construir un AFD que lo acepte: a) L = { w| w contiene un número impar de a′s y un número par de b′s } b) L = { w| w contiene un número par de a′s y un número par de b′s } c) L = { w| w contiene un número impar de a′s y un número impar de b′s } d ) L = { w| w contiene un ab o ba como subpalabras } e) L = { w| w contiene un ab y ba como subpalabras } f ) L = { w| w contiene un ab ó ba como subpalabras, pero no ambas } TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

12

SOLUCION a) Un diagrama de transición del autómata finito es:

b)Cambiando el estado de aceptación del autómata representado arriba obtenemos el au tómata:

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

13

c) De nuevo cambiando el estado de aceptación obtenemos el autómata correspondiente

d)A continuación un diagrama de transición de un autómata finito determinista que ace pta el lenguaje cuyas palabras contienen las subpalabras ab o ba o ambas

e) Este autómata acepta las palabras que contienen las subpalabras ab y ba

TEORIA DE LENGUAJES

TEORIA DE LENGUAJES UNC

14

f) Este autómata acepta las palabras que contienen las subpalabras ab ó ba, pero no ambas

TEORIA DE LENGUAJES...