Trabajo Práctico nº 2 Lenguajes, Expresiones y Gramáticas Regulares

...

- L = { xy / x ∈ (0,1)+ ∧ (y = cn bm ∨ y = cn di ) ; n ≥ 0; i,m ≥ 1}

ER= ((0/1)+).c*.(b+/d+)

Ejercicio 4.

Considerá las siguientes definiciones regulares definidas sobre

Σ = {-, ., _ ,a, b, c, …, z, A, B,…, Z, 0, 1, …, 9}:

- dígito = 1 / 2 / … / 9

- cero = 0

- numero = cero / dígito

- punto = .

- guión = -

- subrayado = _

- letra = a / b / … / z / A / B / … / Z

Indicá cuál es el lenguaje denotado por cada una de las siguientes expresiones regulares (definirlo conceptualmente:

- número numero* punto número*

Números decimales positivos

- número * ( punto / λ )

Números positivos enteros

- (cero / dígito número* ) punto (cero / número* dígito)

Números positivos decimales y enteros

- letra (letra / número)*

Palabras alfanuméricas (sin guiones)

- letra (letra / número / guión (letra / número))*

Palabras alfanuméricas no finalizadas en guión

- (letra / subrayado) (letra / número / subrayado)*

Una letra o subrayado seguido de letras números y/o subrayados

Ejercicio 5.

Considerá las siguientes expresiones regulares:

α = a* / b*

β = a b* / b a* / b* a / (a* b)*

Encontrá valores de x ∈ {a,b}* tal que

- x ∈ L(α) – L(β)

x= aa

- x ∈ Σ*, tal que x ∈ L(β) – L(α)

x= ba

- x ∈ Σ*, tal que x ∈ L(α) n L(β)

x= a

- x ∈ Σ* – (L(α) U L(β))

x= aba

Ejercicio 6.

Determiná si las siguientes expresiones regulares son equivalentes. En caso afirmativo, indicá las propiedades aplicadas para probar su equivalencia. En caso contrario, dá un contraejemplo.

- λ* / (r1 / r2) . (r1* . r2*)* ≡ (r1 / r2)*

La segunda expresión admite la cadena “r1 r1 r2 r2 r1 r2” y la primer expresión no.

- ((r1 . Ø)* / (r1*) * ≡ r1*

r1.0 = r1 ^ r1** = r1* => r1*/r1* = r1*

SON EQUIVALENTES

- (λ / aa)* ≡ (aa)*

Cualquier cadena concatenada con λ da la misma cadena, (λ/aa)* = (aa)*

SON EQUIVALENTES

- (aa)* a / (aa)* = a+

No son equivalentes por que la 1º expresión soporta λ y la segunda no.

- (aa)* = a+ / λ

No son equivalentes por que la 2º expresión soporta aaa y la primera no.

Ejercicio 7.

Dá, cuando sea posible, una expresión regular que describa los siguientes conjuntos de cadenas:

- {w / w ∈{a, b, c}* y w comienza con a }

ER= λ /(a+.(a/b/c)*)

- { a3i / i >= 0 }

ER= (aaa)*

- ({b} U {c}). ({a} U {b} U {c})*

ER= (b/c).(a/b/c)*

- { a3i bi / i >= 0 }

ER= ¿?

Ejercicio 8.

Generá una expresión regular y una gramática regular para cada uno de los siguientes lenguaje. Indicá cuáles son los criterios tomados. Por ej., para el punto a), se puede decir que tomamos como fecha válida los formatos dd/mm/yyyy o dd-mm-yyyy, o dd-mm-yy, etc.

- Cadenas que representen una fecha válida

ER= (((0.( 1/../9))/(1/2).(0/1/../9))/(3.(0/1))).-. ((0.(1/../9))/(1.(0/1/2))).-.((0/../9).(0/../9))

S → 0A / 1A /1B / 2A /2B / 3B / 3C

A → 1-D/ 2-D/ 3-D/ 4-D/ 5-D/ 6-D/ 7-D/ 8-D/ 9-D

B → 0-D

C → 1-D

D → 0E / 1F

E → 1-G/ 2-G/ 3-G/ 4-G/ 5-G/ 6-G/ 7-G/ 8-G/ 9-G

F → 0-G/ 1-G/ 2-G

G → 0H/ 1H/ 2H/ 3H/ 4H/ 5H/ 6H/ 7H/ 8H/ 9H

H → 0/ 1/ 2/ 3/ 4/ 5/ 6/ 7/ 8/ 9

- Cadenas que representen una hora válida (FORMATO DE HORA HH:MM:SS)

ER= ((((0/1).(0/…/9))/(2.(0/…/3))).:.((0/…/5).(0/.../9)).:. ((0/…/5).(0/.../9))

S → 0A /1A / 2B

A → 0:C/ 1:C/ 2:C/ 3:C/ 4:C/ 5:C/ 6:C/ 7:C/ 8:C/ 9:C

B → 0:C/ 1:C/ 2:C/ 3:C

C → 0D/ 1D/ 2D/ 3D/ 4D/ 5D

D → 0:E/ 1:E/ 2:E/ 3:E/ 4:E/ 5:E/ 6:E/ 7:E/ 8:E/ 9:E

E → 0F/ 1F/ 2F/ 3F/ 4F/ 5F