Skip to content

Instantly share code, notes, and snippets.

@mroman42
Last active August 29, 2015 14:15
Show Gist options
  • Save mroman42/e5f164f6994c0f2f4ffd to your computer and use it in GitHub Desktop.
Save mroman42/e5f164f6994c0f2f4ffd to your computer and use it in GitHub Desktop.
Respuestas a los tests de modelos de computación
# Test 1
1. F
2. F
3. F
4. V
5. F
6. F
7. F
8. V
9. F
10. F
11. V
12. F
13. F
14. V
15. V
16. V
17. F
18. V
19. V
20. V
21. V
# Test 2
1. F
2. F
3. V
4. V
5. F
6. F
7. F
8. V
9. F
10. V
11. F
12. F
13. V
14. V
15. V
16. V
17. V
18. V
19. V
20. V
21. F
22. F
23. F
24. F
25. V
# Test 3
1. F
2. V
3. V
4. V
5. F
6. F
7. F
8. F
9. F
10. V
11. V
12. V
13. V
14. V
15. F
16. F
17. V
18. V
19. V
20. V
21. F
22. V
23. F
24. V
25. V
26. V
27. V
28. F
29. F
30. F
31. F
32. F
33. V
34. V
35. F
36. V
37. V
38. V
39. F
40. V
41. F
42. V
43. V
44. V
45. V
# Test 4
1. F
2. F
3. F
4. V
5. V
6. V
7. F
8. V
9. F
10. V
11. V
12. V
13. F
14. F
15. F
16. F
17. F
18. V
19. F
20. F
21. F
22. V
23. V
24. F
25. F
# Tema 5
1. F
2. F
3. F
4. F
5. V
6. V
7. V
8. F
9. F
10. V
11. F ?
12. F
13. F
14. V
15. F
16. V
17. F
18. V
19. V
20. V
21. V
22. F
23. F
24. V
25. F
26. F
27. F
28. V
29. F
30. F
# Tema 6
1. F
2. V
3. F
4. F
5. F
6. F
7. V
8. V
9. F
10. V
11. F
12. V
13. F
14. F
15. V
16. F
17. V
18. V
19. F
20. V
21. V
22. F
23. V
24. V
25. V
26. V
27. F
28. V
29. V
30. V
31. V
32. F
33. V
34. F
35. F
36. V
37. V
38. V
39. F
@oxcar103
Copy link

En el test 1, pregunta 2, al decir verdadero, afirmas que no existen lenguajes con un número finito de palabras o lo he interpretado mal?

@oxcar103
Copy link

En el test 2, la pregunta 20 es verdadera ya que los autómatas finitos deterministas(AFD) son autómatas finitos no deterministas(AFND), como se dice en la demostración de la equivalencia de que un lenguaje puede ser aceptado por un AFD ↔️ puede ser aceptado por un AFND.
La pregunta 21(y la 22 ya que no veo la diferencia entre ambas) es falsa, ya que también es necesario añadir un nuevo estado inicial, hacerlo final, y ponerle una transición nula al antiguo estado inicial.

@fdavidcl
Copy link

Te discuto algunas, corrígeme si me equivoco:

  • 1.2: Para el alfabeto A = {a}, un lenguaje es L = {a}, que es finito ¿no? ¿O la pregunta habla de A*?
  • 1.3: Para el lenguaje L = {ε}, L* = L finito.
  • 1.11: No sé muy bien que es exactamente la cabecera de L, pero como A* incluye ε, entonces L debe estar en Cab(L), porque L{ε} está contenido en L. No estoy seguro de esto.
  • 2.20: Entendiendo por "autómata finito" el dibujo del autómata finito, entonces cualquier dibujo de uno determinista lo es también de uno no determinista.
  • 2.21, 2.22: Si haces lo que dicen los enunciados no tienes por qué estar aceptando ε, que está en L*, ¿no?

Ahora me pongo con los siguientes tests.

Edit: No había visto las respuestas de Óscar.

@MartaAndres
Copy link

Coincido con lo que ha dicho David de la 1.11
La cabecera, por la definición de las transparencias es
CAB(L)={u | u en A* y existe v en A* tal que uv pertenecen a L}
Tomando siempre v=ε, te sale que L está en la cabecera.

@mroman42
Copy link
Author

Voy corrigiendo:

  • 1.2, 1.3, 1.11, 2.21, 2.22. Verdad. Errores míos.
  • 2.20. Parece lo más sensato, pero no tengo claro cómo está planteada.

@MartaAndres
Copy link

Sobre el test 3:

  • 15: Es falsa seguro. Puedes tener todos los ciclos que quieras, que mientras no haya estados finales, el lenguaje va a ser el vacío.
  • 18: Yo diría que es verdadera, porque es el conjunto de palabras que contienen 0011.

EDIT:
Sobre el test 4:

  • 21: Es falso. Yo creo recordar que dijo en clase que había que tener cuidado al numerar porque podía salir bastante más largo. En mis apuntes hay un "! numeración de las variables" que creo que significa eso.

@mroman42
Copy link
Author

Cambio:

  • 15 y 21: De acuerdo en ambos, aunque no tengamos ejemplo explícito del 21, tengo apuntado algo parecido. Quito las "?".
  • 18: Sí, error mío. Entendía la v del enunciado como una u. El -1 de la v está puesto por despistar. Lo cambio.

@oxcar103
Copy link

En el test 5, la pregunta 19 es verdadera, hay un teorema que dice que un lenguaje puede ser aceptado por un AP(autómata con pila) por criterio de pila vacía ↔️ puede ser aceptado por otro AP por criterio de estados finales.

@oxcar103
Copy link

En el test 6, la 7(y la 37) es falsa porque la clase de lenguajes independientes del contexto no es cerrada para el complementario.

@mroman42
Copy link
Author

Cambio:

  • 5.19: Ocurre que no indica si es determinista o no, y en los deterministas no tienes el teorema. Vamos a suponer que si no pone nada es no determinista, que es lo que hacen los apuntes algunas veces. Lo cambio.
  • 6.17, 6.37: No. El -1 es la inversión del lenguaje, no su complementación. Y las FCG son cerradas para inversión porque podemos invertir las producciones.

@MartaAndres
Copy link

Más sobre el test 5:

  • 5: Creo que es verdad, es un poco ambiguo pero yo diría que es suficiente (aunque no necesario). Mirando la definición de un paso de cálculo, se incluyen transiciones nulas. Entonces, la condición de que sólo haya una transición nula si no hay ninguna otra transición se debe cumplir, porque si no habría varias posibles configuraciones que se obtendrían en un paso de cálculo. (La otra condición para ser determinista es trivial.) No sé si lo he explicado muy bien 😕
  • 11: Yo también diría que es falso, porque como decía el de prácticas (creo), no sabes cuándo has llegado al 0011 del centro.
  • 16:Yo entendí que era verdad, porque todas las instrucciones acaban en ";", y ya dijimos que si tienes un símbolo final que no aparece en resto de la instrucción, entonces cumple la propiedad prefijo.
  • 17: Falso, yo diría que da lugar a 3^4 producciones, no 4^3.
  • 23: Falso porque no dice lo que se ha consumido de la cadena de entrada.

EDIT:
Sobre el tema 6:

  • 6: Yo diría que es falso, porque si comparas i con j, ya no puedes comparar j con k.
  • 10 y 12: Por completar, una búsqueda rápida en los apuntes dice que son las dos verdaderas.
  • 16: Yo creo que es falso, porque ni siquiera {uu | u pertenece a {0,1}*} es independiente del contexto. Si lo fuera, ¿cómo comparas dos palabras con el mismo orden con una pila?
  • 29: Es verdadero, se comprueba directamente por la definición. Lo que es indecidible es comprobar si una gramática es determinista.

@oxcar103
Copy link

Mario, con FCG te refieres a las gramáticas libres de contexto( aunque en wikipedia, las llama context-free grammar (CFG)) o son otras siglas?

@MartaAndres
Copy link

Corrección:
En la 5.5, no hace falta todo lo que he puesto. Sacado directamente de las diapositivas:
Una condición equivalente es que para cada configuración C_1 existe, a lo más, una configuración C_2 tal que C_1 ⊢ C_2 (se puede llegar de C_1 a C_2 en un paso de cálculo)
O sea, que además lo he dicho mal, porque es suficiente y también necesaria.

@mroman42
Copy link
Author

Sí, estoy llamando FCG a eso. ¿Dónde lo habré leído yo así?

Cambios:

  • 5.5, 5.17, 5.23: Exacto. Aquí quería segunda opinión. Quito los "?"
  • 5.11: ¿Demostración sencilla tenéis alguno?
  • 5.16: Error mío.
  • 6.6: ¿Demostración sencilla? No se me ocurrió nada rápido.
  • 6.10, 6.12: Luego podemos mandar esto, lo hemos revisado entre varios y lo acabas de completar.
  • 6.16, 6.29: Es falso e hice demostración por bombeo. Error al copiar ambos.

@MartaAndres
Copy link

La 5.25 han dicho por el grupo que es falsa.

La 6.6 creo que se puede demostrar con el lema de bombeo, tomando para n la palabra 0^n 1^n 2^n. Tomes como tomes u y x, i=0 o i=2 dan problemas.

@ivancalle
Copy link

3.14 alguien ha conseguido una grámatica regular. Esque nose si lo estoy haciendo bien el lema de bombeo pero si tomamos 1^(2n+1) y u=(vacio) v=1 y w=1^2n y I=2, entonces me queda 1^2(n+1) que no pertenece al lenguaje por tanto el lenguaje no seria reguilar no?

Pd: perdon por ponerlo sin formulita pero esk nose utilizar esto

@mroman42
Copy link
Author

  • 5.25: Entendía que se refería a uno con pila, pero en los apuntes le llama eso sólo al eNFA. Cambio.
  • 6.6: Ah, genial, se puede usar i=0. Qué bonico, gracias.

@mroman42
Copy link
Author

  • 3.14: Fíjate que la diferencia es impar ssi la longitud de la cadena es impar. Y eso sale con:
    (0+1) ((0+1)(0+1))*
    Por ejemplo. El usar así bombeo no funciona porque la partición no la puedes elegir, tendrías que probar que para cualquier partición funciona; y de hecho, para las que toman v con longitud par, no funciona.

PD: A las malas, en el foro se lee mejor que aquí y se puede usar MathJax.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment