teoria de la computacion

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 palabrasde 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 que inician con a2 o que finalizan con b2.
b) El Lenguaje de las cadenas que inician con a2y 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 generetodas 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 reglas de producción más comunes de Lenguaje C en BNF y otras 4 reglas de Pascal en Diagramas de Sintaxis.

22.- Diseñar las composiciones en BNF para una Gramática que...