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

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.

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.

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.

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.

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.

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.