Respuestas a los tests de modelos de computación

testsMC

# 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

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?

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.

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.

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.

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

• 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.

• 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.