Altillo.com > Exámenes > UBA - Ingeniería > Matemática Discreta

1) Dado
Se pide
a) e.r. (si existe), si no, justificar.
b) aceptor del lenguaje.
c) Gramática que lo genera.
d) Tipo de lenguaje. Justificar.

2) Dada la siguiente gramática
G_
VT = {a, b, c} VA = {S, A, B}

Se pide
a) L
b) Tipo lenguaje.
c) e.r. (si existe), sino justificar.
d) aceptor del lenguaje.
e) ¿es ambigua la gramática? Justificar.
f) ¿es inherentemente ambiguo el lenguaje?

3) Máquina de Turiag que acepte el lenguaje de 1)

4) Trazar, si es posible, grafos que verifiquen las siguientes condiciones. Si no es posible, justificar.
a) Un grafo no orientado sin ciclos de Hamilton pero que si sea un grafo de Euler.
b) Un grafo de Euler que en cada vértice el grado exterior sea mayor que el grado interior.
c) Un grafo no orientado cuyos vértices tengan respectivamente grados 0, 1, 2, 5, 6, 3.

Respuestas abajo.

1_a) L no tiene e.r.

c)

d) El lenguaje es no regular.

2_b) El lenguaje es regular.

c)

d)

e) Si, porque puedo generar una sorta por dos caminos distintos, ej:

f) No es inherentemente ambiguo, porque puedo construir otra gramática que no sea ambigua:

3)

4_a)