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
@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