Electricidad

9.1 En cada uno de los incisos determinar si la gramática dada es regular, libre de contexto y/o sensible al contexto. Explique su respuesta.
a) Sea:
T=(x,y,z) N=(s,A,B,C)
Composiciones:
s→xs A→xA B→xA C→xC C→y
s→zB A→yC B→yC C→zA A→y
s→yA A→zB B→zs C→yB s→z

b) Sea:
T=(x,y,z) N=(s,A,B)
Composiciones:
s→yAA→xBA B→Bx
BxA→ xAz→CB B→Ayy
A→yz Cy→zz B→xx

c ) Sea:
T=(x,y) N=(s,A,B,C)
Composiciones:
S→xB B→yxC C→BxA
A→xBy B→yyC C→xy
A→CBx B→x A→y


9.2 en cada uno de los incisos determinar si la gramática dada es regular, libre de contexto y/o sensible al contexto. Explique su respuesta.

Sea:
T={x,y,z} N={s,A,B,C,D}

Composiciones:
s →BxA B→ yCx C→ BA C→ yx
AA →zBC Ay →xy Bx→DyA BA→ yzz
Dyz→ CD DB →xAC CC →yyzx Cxx →zyB

Sea:
T= {x,y} N={s,A,B,C}

Composiciones:
s→yA A → xAB A→ Bxx A→ yx
B →xBy B → Ayy C→ x
A →xC B → yC B→ y
c) Sea:
T= {0,1} N={s,A}

Composiciones:
S→0A1 A→0A1 A→ 01 A →10
S→1A0 A→1A0 A→10A A→01A


9.3 En cada una de las gramáticas del problema 9.1 realizar lo siguiente:
a) Con la gramática del inciso a):
-Derivar las palabras: zyxzzzz, usando para ello las composiciones y también por medio de un árbol de derivación.
-Representar dicha palabra con notación BNF
b) Con la gramática del inciso b):-Derivar la palabra yzzzyyxx usando para ello las composiciones
-Representar dicha palabra con notación BNF

c) Con la gramática del inciso c):
-Derivar la palabra xyyyyxyxxyxx usando para ello las composiciones
-Por medio de un árbol de derivación, probar que la palabra xyyyyxyxxyxx pertenece al lenguaje.
-Representar dicha palabra con notación BNF
-Representar la gramática por medio dediagramas sintácticos.
9.4en cada una de las gramáticas del problema 9.2 realizar lo siguiente:
a) con la gramática del inciso a):

derivar usando composiciones las palabras siguientes: zyyyzx, zyyyxxyyzx con la finalidad de determinar si pertenecen al lenguaje
representar dicha gramática con notación BNF.

b) con la gramática del inciso b):
derivar usando para ello composiciones lapalabra:
yxxxxyxxyyy.
Por medio de un árbol de derivación, probar que la palabra yxxxxyxxyyy pertenece al lenguaje.
representar dicha gramática con notación BNF.
Representar la gramática usando diagramas sintácticos

C) con la gramática del inciso c)
Derivar usando composiciones las palabras: 010011, 1111000, 01011010
Por medio de arboles de derivación, probar que las palabras 010011,1111000, 01011010pertenecen al lenguaje
Representar dicha gramática con notación BNF.

Representar la gramática usando diagramas sintácticos.

9.5 Sean:
∑=(0,1);L=(3,0,1,00,10,111);M=(1,00,01,100,111,000)
Encontrar:
a) L U M d)L-M g)L2 j)L
b) L ∩ M e)Ml h)L+
c) LM f)Ll i)L*


9.6 sean:
∑= {0,1}; L= {0, 11, 100}; M= {1, 00, 01, 100,111, 000}
Encontrar:
a) LI
b) MI
c) L+
d) M+
e) MI
f) L2
g) M3
h) (LυMI)
i) (M-L)
j) LM
k) M’
l) (M’) I

9.7 Sean:
∑=(a,b,…,z); L=(días) Encontrar:
a)L+ d)(L+)2 g)(L*)I j) (L)I
b)L* e)(L+)I h)(LI)* k)(L*)’
c)LI f)(LI)+ i)L’ l)(L+)I

9.8 Sean:
∑= (0,1); L ={110}. Encontrar
a) L*
b) L*
c) LI
d)L4
e) (LI)3
f) (L*)I
g) (LI)+
h) (L+)*
i) (L+)+
j) (L*)*
k) (L*)’
l) (L+)’


9.9 Sean M y L Lenguajes regulares sobre ∑ Probar que las siguientes equivalencias de expresiones regulares son ciertas:
a) (LM*)IU(M0UM+)ILI=(M*)ILI
b) ((EUM)*((L+)+ULL*))I=(L+)I(M+)I
9.10 sean MyL lenguajes regulares sobres ∑ demostrar que los siguietes lenguajes son equivalentes.
a) (( Ø*υL)*)...