Trabajo Práctico nº 2 Lenguajes, Expresiones y Gramáticas Regulares
Enviado por Stella • 20 de Noviembre de 2018 • 1.435 Palabras (6 Páginas) • 370 Visitas
...
- 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
...