Diferencia entre revisiones de «Práctica 1: Gramáticas Regulares y Autómatas Finitos (Teoría de Lenguajes)»
De Cuba-Wiki
(No se muestran 5 ediciones intermedias del mismo usuario) | |||
Línea 6: | Línea 6: | ||
*a) ''Constantes reales con signo'' | *a) ''Constantes reales con signo'' | ||
S->+A|-A | S -> +A | -A | ||
A->0,C|1..9B | A -> 0,C | 1..9B | ||
B->0..9B|,C|λ | B -> 0..9B| ,C | λ | ||
C->0..9C|1..9 | C -> 0..9C| 1..9 | ||
S -> +A | -A | |||
A -> E | E,D | |||
E -> 0 | E' | |||
E' -> 1..9 | E'0..9 | |||
D -> 1..9 | 0..9D | |||
*b) <math>L = {x = a^i b^j \vee x = (cd)^{2n+2}, i \geq 0, n,j \geq 1}</math> | *b) <math>L = {x = a^i b^j \vee x = (cd)^{2n+2}, i \geq 0, n,j \geq 1}</math> | ||
S-> | S -> Ab | cdcdcdB | ||
A-> | A -> aA | Ab | λ | ||
B->cdcdB | λ | B -> cdcdB | λ | ||
*c) ''Cadenas que contengan 3 ceros consecutivos.'' | *c) ''Cadenas que contengan 3 ceros consecutivos.'' | ||
S-> | S -> 0A | 1S | ||
A -> 0B | 1S | |||
C -> 0C | 1S | |||
C -> 0C | 1S | λ | |||
*d) ''Cadenas que representen una fecha valida de este siglo (p. ej, 29/2/01 es invalida)'' | *d) ''Cadenas que representen una fecha valida de este siglo (p. ej, 29/2/01 es invalida)'' | ||
Línea 26: | Línea 35: | ||
| 31/(1,3,5,7,8,10,12)/(00..99) | | 31/(1,3,5,7,8,10,12)/(00..99) | ||
*e) ''Cadenas que representen una hora valida (p. ej, 23:60 es invalida)'' | *e) ''Cadenas que representen una hora valida (p. ej, 23:60 es invalida)'' | ||
S-> | S -> B:CB | 1B:CB | 2D:CB | ||
B -> 0 | ... | 9 | |||
C -> 0 | ... | 5 | |||
C-> | D -> 0 | ... | 3 | ||
D-> | |||
==Ejercicio 02== | ==Ejercicio 02== | ||
==Ejercicio 03== | ==Ejercicio 03== | ||
==Ejercicio 04== | ==Ejercicio 04== |
Revisión del 03:42 9 dic 2009
Ejercicio 01
Construir gramaticas regulares para los siguientes lenguajes:
- a) Constantes reales con signo
S -> +A | -A A -> 0,C | 1..9B B -> 0..9B| ,C | λ C -> 0..9C| 1..9
S -> +A | -A A -> E | E,D E -> 0 | E' E' -> 1..9 | E'0..9 D -> 1..9 | 0..9D
- b)
S -> Ab | cdcdcdB A -> aA | Ab | λ B -> cdcdB | λ
- c) Cadenas que contengan 3 ceros consecutivos.
S -> 0A | 1S A -> 0B | 1S C -> 0C | 1S C -> 0C | 1S | λ
- d) Cadenas que representen una fecha valida de este siglo (p. ej, 29/2/01 es invalida)
S->(1..28)/(1..12)/(00..99) | 29/(1,3..12)/(00..99) | 29/2/(00,04..96) | 30/(2,4,6,9,11)/(00..99) | 31/(1,3,5,7,8,10,12)/(00..99)
- e) Cadenas que representen una hora valida (p. ej, 23:60 es invalida)
S -> B:CB | 1B:CB | 2D:CB B -> 0 | ... | 9 C -> 0 | ... | 5 D -> 0 | ... | 3