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

De Cuba-Wiki

Plantilla:Back

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

Ejercicio 02

Ejercicio 03

Ejercicio 04

Ejercicio 05

Ejercicio 06