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

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?

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.

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.

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.

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.

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.

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.