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

• b) $L={x=a^{i}b^{j}\vee x=(cd)^{2n+2},i\geq 0,n,j\geq 1}$

S->aS | bA | cdcdcdB
A->bA | λ
B->cdcdB | λ

• c) Cadenas que contengan 3 ceros consecutivos.

S->(0,1)S | 000A, A->(0,1)A, A->λ

• 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->(0,1)A | 2E
A->(0..9)B
B->:C
C->(0..5)D
D->(0..9)
E->(0..3)B