MODELOS DE COMPUTACION I Preguntas Tipo Test Indicar si son verdaderas o falsas las siguientes afirmaciones: 1. El lema de bombeo puede usarse para demostrar que un lenguaje determinado es regular. 2. Todo lenguaje con un n´ umero finito de palabras es regular. 3. La clase de los lenguajes aceptados por los aut´omatas con pila deterministas es igual a la clase de los lenguajes generados por las gram´ aticas de tipo 2. 4. Si un lenguaje de tipo 2 viene generado por una gram´ atica ambigua, siempre puedo encontrar una gram´ atica no ambigua que genere el mismo lenguaje. 5. La intersecci´on de lenguajes regulares es siempre regular. 6. La intersecci´on de lenguajes libres de contexto es siempre libre de contexto. 7. La demostraci´on del lema de bombeo se basa en que si leemos una palabra de longitud mayor o igual al n´ umero de estados del aut´ omata, entonces en el camino que se recorre en el diagrama de transici´on se produce un ciclo. 8. En una gram´ atica de tipo 2 ambigua no puede existir una palabra generada con un u ´ nico ´arbol de derivaci´ on. 9. Una palabra es aceptada por un aut´ omata con pila por el criterio de pila vac´ıa si en alg´ un momento, cuando leemos esta palabra, la pila se queda sin ning´ un s´ımbolo, con independencia de la cantidad de s´ımbolos que hayamos le´ıdo de la palabra de entrada. 10. Dada una gram´ atica libre de contexto, siempre se puede construir una gram´ atica sin transiciones nulas ni unitarias que genere exactamente el mismo lenguaje que la gram´ atica original. 11. Si un lenguaje es generado por una gram´ atica dependiente del contexto, entonces dicho lenguaje no es independiente del contexto. 12. Los alfabetos tienen siempre un n´ umero finito de elementos, pero los lenguajes, incluso si el alfabeto tiene s´ olo un s´ımbolo, tienen infinitas palablas. 13. Es m´as f´ acil determinar si una palabra pertenece a un lenguaje regular cuando ´este viene dado por una expresi´ on regular que cuando viene dado por un aut´omata finito determinista. 14. Un aut´omata con pila siempre acepta el mismo lenguaje por los criterios de pila vac´ıa y de estados finales. 15. Existe un algoritmo para determinar si una palabra es generada por una gram´ atica independiente del contexto. 16. El lenguaje {ai bj ci di : i, j ≥ 0} es independiente del contexto. 17. En la demostraci´on de que todo aut´ omata finito tiene una expresi´ on regular que representa el mismo k lenguaje, el conjunto Rij se define como el lenguaje de todas las palabras que llevan al aut´omata del estado qi al estado qj pasando por el estado n´ umero k, qk . 18. La demostraci´on de que la clase de lenguajes aceptados por los aut´omatas no deterministas es la misma que la aceptada por los aut´ omatas determistas, se basa en dado un aut´omata no determinista construir uno determinista que, ante una palabra de entrada, explore todas las posibles opciones que puede seguir el no determinista. 1

19. Existe un algoritmo para determinar si una gram´ atica independiente del contexto es ambigua. 20. Una gram´ atica independiente del contexto es ambigua si existe una palabra que puede ser generada con dos cadenas de derivaci´ on distintas. 21. El conjunto de todas las expresiones regulares es un lenguaje regular. 22. Todo lenguaje aceptado por un aut´ omata con pila determinista por el criterio de estados finales es tambi´en aceptado por una aut´ omata con pila determinista por el criterio de pila vac´ıa. 23. Si L es un lenguaje no vac´ıo, entonces L∗ es infinito. 24. A partir de la demostraci´on de que si R es regular y L un lenguaje cualquiera, entonces R/L es regular, se puede obtener un algoritmo para construir el aut´omata asociado a R/L. 25. En un aut´ omata finito no-determinista, si intercambio entre s´ı los estados finales y no finales obtengo un aut´omata que acepta el lenguaje complementario. 26. Existe un algoritmo para comprobar cuando dos gram´ aticas libres de contexto generan el mismo lenguaje. 27. Si en un aut´ omata finito no hay estados distinguibles de nivel 2, ya no puede haber estados distinguibles de nivel 4. 28. El lenguaje L = {0i 1j 2k : 1 ≤ i ≤ j ≤ k} es independiente del contexto. 29. Un lenguaje inherentemente ambiguo puede ser generado por una gram´ atica ambigua. 30. Para que un aut´ omata con pila sea determinista es suficiente que desde cada configuraci´on se pueda obtener, a lo m´as, otra configuraci´on en un paso de c´ alculo. 31. Todo lenguaje con un n´ umero finito de palabras es regular e independiente del contexto. 32. Todo lenguaje generado por una gram´ atica lineal por la derecha es tambi´en generado por una gram´ atica lineal por la izquierda. 33. Si r y s son expresiones regulares, tenemos que siempre se verifica que (rs)∗ = r∗ s∗ 34. Si r y s son expresiones regulares, tenemos que siempre se verifica que (r + s)∗ = r∗ + s∗ 35. Si un lenguaje de tipo 2 verifica la propiedad prefijo y es aceptado por un aut´omata con pila determinista por el criterio de estados finales, entonces tambi´en es aceptado por un aut´omata con pila determinista por el criterio de pila vac´ıa. 36. Si el lenguaje L es independiente del contexto, entonces L−1 es independendiente del contexto. 37. Existe un algoritmo que permite determinar si una gram´ atica independiente del contexto genera un lenguaje finito o infinito. 38. Existe un algoritmo para determinar si una gram´ atica independiente del contexto es ambigua. 39. Para todo aut´ omata con pila existe otro aut´omata con pila que acepta el mismo lenguaje y tiene un solo estado. 40. Un aut´omata finito determinista sin estados inaccesibles ni indistinguibles es minimal. 41. Si L es un lenguaje, entonces siempre L∗ es distinto de L+ .

2

42. Si un lenguaje es aceptado por una aut´omata con pila determinista por el criterio de estados finales, entonces tambi´en es aceptado por un aut´omata con pila determinista por el criterio de pila vac´ıa. 43. Si L es una lenguaje sobre el alfabeto A, entonces CAB(L) es siempre igual al cociente L/A∗ . 44. En el algoritmo de Early, la presencia del registro (2, 5, A, CD, adS) implica que a partir de CD se puede generar la subcadena de la palabra de entrada que va del car´ acter 3 al 5. 45. El lenguaje de las palabras sobre {0, 1} con un n´ umero impar de ceros es independiente del contexto. 46. El lenguaje de las palabras sobre {0, 1} en las que la diferencia entre el n´ umero de ceros y unos es impar es regular. 47. En un aut´ omata finito cualquiera, si las transiciones dan lugar a un ciclo, entonces el lenguaje aceptado es infinito. 48. Si en una producci´on de una gram´ atica independiente del contexto, uno de los s´ımbolos que contiene es u ´ til, entonces la producci´on es u ´ til. 49. En un aut´ omata con pila determinista no puede haber transiciones nulas. 50. Si r1 y r2 son expresiones regulares, tales que su lenguaje asociado contiene la palabra vac´ıa, entonces (r1 r2 )∗ = (r2 r1 )∗ . 51. L.∅ = L 52. La expresi´ on recursiva que se emplea para obtener la expresi´ on regular asociada a un aut´omata finito k−1 k−1 k−1 ∗ k−1 k determinista es: rij = rij + ri(k−1) (r(k−1)(k−1) ) r(k−1)j 53. Si r y s son expresiones regulares, tenemos que siempre se verifica que (r + ǫ)+ = r∗ 54. Si r y s son expresiones regulares, tenemos que siempre se verifica que r(r + s)∗ = (r + s)∗ r 0 55. Cuando se construye la expresi´ on regular asociada a un aut´omata finito determinista, rii no puede ser nunca vac´ıo.

56. Existe un algoritmo para comprobar si el lenguaje generado por una gram´ atica libre de contexto es regular. 57. El algoritmo de Early se puede aplicar a cualquier gram´ atica independiente del contexto (sin producciones nulas ni unitarias). 58. Si L es independiente del contexto determinista y $ 6∈ L entonces L.{$} es aceptado por un aut´omata con pila determinista por el criterio de pila vac´ıa. 59. Todo ´arbol de derivaci´ on de una palabra en una gram´ atica independiente del contexto est´ a asociado a una u ´ nica derivaci´ on por la izquierda. 60. El conjunto de las palabras {u0011v −1 : u, v ∈ {0, 1}∗} es regular. 61. El conjunto de las palabras {u0011u−1 : u ∈ {0, 1}∗} es libre del contexto determinista. 62. Si L es un lenguaje finito, entonces su complementario es siempre regular. 63. Si r1 y r2 son expresiones regulares, entonces r1∗ r2∗ ⊆ (r1 r2 )∗ , en el sentido de que los lenguajes asociados est´ an incluidos. 64. Un aut´omata finito puede ser determinista y no-determinista a la vez. 3

65. En un aut´ omata finito determinista la relaci´on de indistinguibilidad es una relaci´on de equivalencia. 66. En la construcci´ on de una gram´ atica independiente del contexto a partir de un aut´omata con pila, la variable [p, X, q] genera todas las palabras que llevan al aut´omata desde el estado p al estado q sustituyendo X por el s´ımbolo inicial de la pila. 67. En un aut´ omata finito determinista siempre debe de existir, al menos, un estado de error. 68. Para poder aplicar el algoritmo que hemos visto para transformar una gram´ atica a forma normal de Greibach, la gram´ atica tiene que estar en forma normal de Chomsky necesariamente. 69. El conjunto de palabras {an bn ci : i ≤ n} es independiente del contexto. 70. El conjunto de los n´ umeros en binario que son m´ ultiplos de 7 es regular. 71. Si A es un afabeto, la aplicaci´ on que transforma cada palabra u ∈ A∗ en su inversa es un homomorfismo de A∗ en A∗ . 72. Si ǫ ∈ L, entonces L+ = L∗ . 73. Si r1 , r2 y r3 son expresiones regulares, entonces (r1 + r2 )∗ r3 = r1∗ r3 + r2∗ r3 . 74. Si L1 y L2 son independientes del contexto, entonces L1 − L2 es siempre independiente del contexto. 75. Hay situaciones en las que los estados inaccesibles de un AFD cumplen una funci´ on espec´ıfica. 76. En un aut´ omata con pila determinista no puede haber transiciones nulas. 77. S´ olo hay una derivaci´ on por la derecha asociada a un ´arbol de derivaci´ on. 78. Hay lenguajes que no son libres de contexto y si verifican la condici´on que aparece en el lema de bombeo para lenguajes libres de contexto. 79. El conjunto de palabras {u011u : u ∈ {0, 1}∗ } es independiente del contexto. 80. El conjunto de palabras que contienen la subcadena 011 es independiente del contexto. ∗

81. La transformaci´ on que a cada palabra sobre {0, 1} le a˜ nade 00 al principio y 11 al final es un homomorfismo. 82. Se puede construir un programa que tenga como entrada un programa y unos datos y que siempre nos diga si el programa leido termina para esos datos. 83. La cabecera del lenguaje L siempre incluye a L. 84. Si r1 y r2 son expresiones regulares entonces: (r1 ∗ r2 ∗ )∗ = (r1 + r2 )∗ 85. Para transformar un aut´ omata que acepta el lenguaje L en uno que acepte L∗ , basta unir los estados finales con el inicial mediante transiciones nulas. 86. Para una misma entrada, una m´aquina de Mealy y una de Moore producen salidas de la misma longitud. 87. Si R es un lenguaje regular y L un lenguaje independiente del contexto, entonces R/L es regular. 88. Si en un aut´ omata dos estados son distinguibles de nivel n, entonces ser´ an distinguibles de nivel m para todo m ≥ n.

4

89. Si una gram´ atica independiente del contexto no tiene producciones nulas ni unitarias, entonces si u es una palabra de longitud n generada por la gram´ atica, su derivaci´ on se obtiene en un n´ umero de pasos no superior a 2n − 1. 90. Todo aut´ omata con pila determinista que acepta un lenguaje por pila vac´ıa se puede transformar en otro aut´ omata determinista que acepte el mismo lenguaje por el criterio de estados finales. 91. En el algoritmo de Cocke-Younger-Kasami calculamos los conjuntos Vij que son las variables que generan la subcadena de la palabra de entrada que va desde el s´ımbolo en la posici´ on i al s´ımbolo en la posici´ on j. 92. Si A es un alfabeto, entonces A+ no incluye nunca la palabra vac´ıa. 93. Un lenguaje nunca puede ser igual a su inverso. 94. La aplicaci´ on que transforma cada palabra u sobre el alfabeto {0, 1} en u3 es un homomorfismo. 95. Si r1 y r2 son expresiones regulares, entonces (r1 .r2 )∗ = (r1 + r2 )∗ . 96. Para pasar de un aut´ omata que acepte el lenguaje asociado a r a uno que acepte r∗ basta con unir con transiciones nulas sus estados finales con el estado inicial. 97. Para pasar de una m´aquina de Mealy a una de Moore equivalente, lo que hemos hecho es repetir cada uno de sus estados para cada uno de los posibles s´ımbolos del alfabeto de salida. 98. Si h es un homomorfismo y h(L) no es regular, podemos concluir que L no es regular. 99. Cada ´arbol de derivaci´ on de una palabra en una gram´ atica de tipo 2, tiene asociada una u ´ nica derivaci´ on por la izquierda de la misma. 100. El lenguaje de todas las palabras en las que los tres primeros s´ımbolos son iguales a los tres u ´ ltimos es regular. 101. Para que un lenguaje independiente del contexto sea determinista ha de verificar la propiedad prefijo. 102. Existe un lenguaje reconocido por un AFD y no generado por una gram´ atica independiente del contexto. 103. El lenguaje compuesto por las instrucciones completas del lenguaje SQL cumplen la propiedad prefijo. 104. Existen lenguajes aceptados por AFD que no pueden ser aceptados por AF no determin´ısticos. 105. Un lenguaje puede cumplir la negaci´ on de la condici´on que aparece en el lema de bombeo para lenguajes independientes del contexto y ser regular. 106. La clausura de un lenguaje aceptado por un AFD puede ser representado con una expresi´ on regular. 107. Existe un algoritmo para comprobar si el lenguaje generado con una gram´ atica independiente del contexto es finito o infinito. 108. En el algoritmo para pasar un aut´ omata con pila a gram´ atica que hemos visto, si el aut´omata tiene 3 estados, entonces la transici´on (p, XY ZU ) ∈ δ(q, ǫ, H) da lugar a 43 producciones. 109. Si r es una expresi´ on regular, entonces r∗ r∗ = r∗ . 110. Si L es un lenguaje, entonces siempre est´ a incluido en su cabecera. 111. El lenguaje {0i 1k 2i : i, k ≥ 0} es independiente del contexto determinista.

5

112. Un lenguaje representado por una expresi´ on regular siempre puede ser reconocido por un AF no determinista. 113. Existe un lenguaje con un n´ umero finito de palabras que no puede ser generado por una gram´ atica libre de contexto. 114. Si L1 y L2 son lenguajes independientes de contexto, entonces (L1 L2 ∪ L1)∗ es independiente de contexto. 115. La gram´ atica compuesta por las reglas de producci´on S → AA, A → aSa, A → a no es ambigua. 116. Si tenemos un lenguaje L aceptado por un Aut´omata con Pila por el criterio de estados finales, podemos encontrar otro AP que reconozca L por el criterio de pila vac´ıa. 117. La propiedad prefijo no tiene ninguna relaci´on con el hecho de que un lenguaje sea aceptado por un aut´omata con pila determinista por estados finales. 118. Si L1 y L2 son lenguajes independientes de contexto, entonces (L1 − L2 ) es independiente del contexto. 119. Para poder aplicar el algoritmo que transforma una gram´ atica en forma normal de Greibach es necesario que la gram´ atica est´e en forma normal de Chomsky. 120. Si un lenguaje verifica la condici´on que aparece en el lema de bombeo para lenguajes regulares, ya no hay forma de demostrar que no es regular. 121. Si r es una expresi´ on regular, entonces r∅ = r + ∅.

6