Tarea de investigacion IV

 1.- Generar la gramática regular que considere cadenas de longitud 3 sobre el alfabeto de terminales ΣT = {a, b}.
SaB|bB
BbC|aC
Ca|b
2.- Dada la siguiente gramática G, determinar ellenguaje que genera:
G = ({a,b,c}, {S,A,B,C}, S, P),
P = { S::= aA | aB | aC | bB | bC | cC | a | b | c | λ , A::= aA | aB | aC| a, B::= bB | bC | b, C::= cC | c }
L= {a*b*c*}
3.- Dada la siguientegramática G, determinar el lenguaje que genera:
G = ({a,b,c}, {S,A,B}, S, P),
P = { S::= aA | cB, A::= aS, B::= aB | bB | a | b }
L= {(aa)*c(a,b)*}
4.- Para cada uno de los siguientes lenguajes,da DOS cadenas que pertenezcan y DOS que NO SEAN miembros (un total de cuatro cadenas para cada inciso). Asume que el alfabeto es Σ={a,b}
5.- Escriba expresiones regulares para los siguienteslenguajes.
a) El conjunto de cadenas formadas por 0s y 1s cuyo décimo símbolo por la derecha sea 1.
L= 1(0,1)*
b) El conjunto de cadenas formadas por 0s y 1s con máximo una pareja de 1s consecutivos.L= (0,10)*11(0,01)*
c) El conjunto de cadenas formadas por ceros y unos cuyo número de ceros es divisible por cinco.
a) a*b*
Validas
ab
λ
Invalidas
bba
aba
b) a(ba)* b
Validas
ababab
Invalidas
bab
ababa
c) a* ∪ b*
Validas
λ
aa
Invalidas
aba
ba

d) (aaa) *
Validas
λ
aaaaaa
Invalidas
aaaa
aaaaa
e) Σ*a Σ*b Σ*a Σ*
Validas
aba
aabbaab
Invalidas
aaaabbbbb
f) aba ∪ bab
Validas
aba
bab
Invalidas
ababab
ababab

L= {(1*01*01*01*01*01*)+
d) El conjunto de cadenas del alfabeto {a, b, c} que contienen al menos una a y al menos una b.
6.-Proporcione las descripciones informales de los lenguajes correspondientes a las siguientes expresiones regulares:
a) (0*1*)* 000 (0 + 1)*
Cadenas que pueden iniciar con 0 o 1 y continuarindefinidamente y terminar con una cantidad similar de 0 o 1 pero entre los dos tiene siempre tres 0.
b) (0 ∪ 10)*1*
Cadenas que pueden iniciar con 0 o 10 indefinidamente seguidos de 1 indefinidos o...