Problemas de teoria de compu

REACTIVOS DE TEORÍA DE LA COMPUTACIÓN

01.- Dado el Lenguaje L = { (, cb, abbc, babac } determinar:
a) Los posibles prefijos, infijos y posfijos de cada cadena.
b) El alfabeto ( y además la longitud de cada cadena de L.
c) El contenido del conjunto L2.
d) ¿Es un Lenguaje finito o infinito?

02.- Dado el Lenguaje L = { (, a, ab, c }, determinar el contenido de los conjuntos(, L0, L1, L2, L+ y L*.

03.- Considérese el lenguaje L*, surgido a partir de L = { a, b } con un alfabeto ( = {a, b}.
a) ¿Cuántas palabras de ese L* tienen longitudes de 2, de 3, de 4 y de n, respectivamente?
b) Evaluar lo mismo que en el inciso anterior, pero ahora con L = { a, ab, bc }, si ( = { a, b, c }.

04.- Considérese a L = { a, ab, bb }. Las cadenas abbabab, aabab,abbaababbb, ¿son palabras de un Ln?

05.- Dado el Lenguaje L = { aa, aba, baa }, responder:
a) Las cadenas a2ba2, (ba3)2, ba5(ba)2a3 ¿son palabras del Lenguaje L+?
b) ¿Qué características tendrían las cadenas de este L+ (expresadas en Lenguaje Natural)?

06.- Describir en Lenguaje Natural las cadenas que contiene cada uno de los siguientes Lenguajes Formales.
a) L = { 1*0 } d) L= { (1, 00)* }
b) L = { 1*00* } e) L = { (0+1)* }
c) L = { 120* } ( { 021*} f) L = { (0,1)1 ( (0,1)* 00 }

07.- Determinar en cuáles de los siguientes Lenguajes está contenida la cadena 1011.
a) L = { 10*1* } e) L = { (11)* (10)* }
b) L = { 0* (11,10)* } f) L = { 1 (10)* (11)* }
c) L = { (10)* 101 } g) L = { 1+ (01)* 1* }
d) L = { 1* 01 (0,1)1 } h) L ={(1,00)1 ( (01,0)1 ( 1*}

08.- Considerando a ( = { a, b, c }, ¿son equivalentes las parejas de expresiones regulares de cada inciso?
a) ( ( a ( b) c)* y (ac ( bc)*
b) b ( ab ( ac ) y ( ba ( ba ) ( b ( c ).
c) ( a ( b )* a* y (( a ( b) a )*

09.- Especificar la expresión regular para los siguientes Lenguajes sobre ( = { a, b }:
a) El Lenguaje de las cadenas queinician con a2 o que finalizan con b2.
b) El Lenguaje de las cadenas que inician con a2 y que finalizan con b2.

10.- Sea G = { (A, B, C), (a, b, c), (A ( aaA, A ( bB, B ( cCb, B ( cb, C ( bbC, C ( bb), (A)}. Establecer cuáles de las siguientes cadenas pertenecen a L (G).
a) aabcb. d) aaaabcbbb.
b) abbcb. e) aabcbbbbb.
c) aaaabcbb. f) aabccbbbb.

11.- Dada G = ( {a, b, c}, { +, - }, { a ( a +, a ( - c -, b - ( +, b c ( +, b ( a + c, c - ( (, c ( c c, a - c ( + + }, { a }).
a) ¿Qué observaciones se le pueden hacer a esta G?.
b) Caracterizar la Gramática anterior.
c) Encontrar 6 cadenas del Lenguaje L (G).

12.- Sean N = { S, A, B }, T = { a, b }, (0 = { S }. Para cada inciso caracterizar el Lenguaje generado por la Gramática señalada:a) P = { S ( AA | B, A ( aaA | aa, B ( bB | b }.
b) P = { S ( AB | AA, A ( aB | ab, B ( b }.
c) P = { S ( AB | aA, A ( a, B ( ba }.

13.- Caracterizar la Gramática con P={S ( xSz, S ( ySz, S ( (} y (0 = { S }.

14.- Caracterizar la Gramática con composiciones P = { S ( AB, AB ( BA, A ( aA, A ( a, B ( Bb, B ( b} y (0 = { S }.

15.- Diseñar la Gramática que produce
a)L(G) = { 0n1n | n ( ( }.
b) L(G) = { 0n1n | n ( (o}.
c) L(G) = { 0m1n | m, n ( (}.

16.- Diseñar para cada inciso una Gramática que genere todas las cadenas de bits con las siguientes características:
a) Con una cantidad par de 0 y una cantidad par de 1.
b) Con igual cantidad de 0 que de 1.
c) Con más 0 que 1.
d) Con desigual cantidad de 0 que de 1.

17.-Diseñar una Gramática Regular que produzca el Lenguaje L = { 01, 10 }+ con T = { 0, 1 }.

18.- Diseñar la Gramática Regular que produzca, a partir del alfabeto ( = {a, b}, el Lenguaje L(G) = {a*b} ( {a}.

19.- Demostrar que L (G) = { ambmcn | m, n ( ( } es un Lenguaje Libre de Contexto.

20.- Demostrar que L(G) = {0n1n | n ( (} no es Lenguaje Regular.

21.- Expresar al menos 5 de las...