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/(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 | 1 | 2 | 3

Ejercicio 03

Construir autómatas finitos para los siguientes lenguajes:

• g) Cadenas que contengan 3 ceros consecutivos. ∑ = {0,1}.

• h) Cadenas que no contengan dos unos consecutivos. ∑ = {0,1}.

• i) Cadenas con un número impar de ceros y un número par de unos

• j) Cadenas donde en todo prefijo (subcadena inicial) la cantida de ceros difiera de la cantidad de unos en no más de 1. Es decir, para todo prefijo se cumple: $|{\text{cant. de ceros}}-{\text{cant. de unos}}|\leq 1$. ∑ = {0,1}.

Ejercicio 05

Dados automatas finitos para L1 y L2 indicar c´omo construir aut´omatas finitos para los siguientes lenguajes, con las mismas consideraciones que en el ejercicio anterior: (a) L1 U L2 (union) (b) L1 n L2 (interseccion) (c) L1.L2 (concatenacion) (d) L1 \ L2 (resta)

[a] creo un nuevo AFND-\ (automata no deterministico con trans. lambda) talque tenga un estado inicia q_o que una con una transicion lambda a los estados finales de los automatas de L1 y L2 Vale que es la union por la definicion de cadena aceptada en un AFND-\ que dice que

    c es aceptada <==> g(qo,c) pertenece a F , c una cadena
                                             , con g la funcion de transcicion
                                             , qo estado inicial
                                             , F conj de estados finales o aceptores

[idea de lo q deberia ser la demostracion] : vale trivialmente pues la trans lambda obligatoria de qo no modifica a las cadenas de L1 y L2 y cualquier palabra q sea aceptada por cualquiera de los dos automatas lo sera en el nuevo pues por alguno de las dos tranciciones se llegara al estado aceptor.

[b] El automata que deriva de la interseccion se construye de la sigueinte manera : Q = Q1 x Q2 ( prod cartesiano de los estados de L1 y L2) q0 = (q1,q2) (con q1 y q2 siendo los estados iniciales de Q1 y Q2) g( (x,y) , a ) = (g1(x,a),g2(y,a)) con (x,y) pertenece Q F = F1 x F2

[demo] :

[c]

[d] L1 \ L2 = L1 n (L2^c) (L2^c --> L2 complemento , es decir la clasura de Kleene del alfabeto menos L2)

- aplico la interseccion del item b y el complemento de un ejercicio previo