Práctica 1: Gramáticas Regulares y Autómatas Finitos (Teoría de Lenguajes)

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) $L={x=a^{i}b^{j}\vee x=(cd)^{2n+2},i\geq 0,n,j\geq 1}$

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