Have an account?
Skip to Content
Build your own quiz
8 questions
Show Answers
See Preview
- 1. Multiple Choice
Las gramáticas de tipo 0:
Son las relacionadas con los lenguajes regulares.
Son las relacionadas con los lenguajes independientes del contexto.
Son las relacionadas con los lenguajes sensibles al contexto.
Son las relacionadas con los lenguajes recursivamente enumerables.
- 2. Multiple Choice
Una máquina de Turing se representa mediante la siguiente tupla: M = (Q,Σ,Γ,δ,q0,B,F). ¿Qué es F?
Alfabeto de entrada.
Conjunto de estados de aceptación.
Conjunto de símbolos de la cinta.
Conjunto de estados iniciales.
- 3. Multiple Choice
El tiempo de ejecución de una máquina de Turing que simula un computador...
Es siempre polinómico.
Es polinómico si las instrucciones cumplen una serie de reglas.
Es superior a polinómico.
Es O(n).
- 4. Multiple Choice
El lenguaje universal...
Es recursivamente enumerable
Es recursivo
Es recursivamente enumerable y recursivo
- 5. Multiple Choice
Supongamos que P1 se reduce a P2. Entonces:
A) Si P1 es indecidible entonces P2 también lo es.
B) Si P1 no es recursivamente enumerable entonces P2 tampoco lo es.
A y B son falsas.
A y B son ciertas.
- 6. Multiple Choice
Un problema es de clase P si:
Existe una máquina de Turing que lo resuelve.
Existe una máquina de Turing determinista que lo resuelve en tiempo polinómico.
Existe una máquina de Turing no determinista que lo resuelve en tiempo polinómico.
- 7. Multiple Choice
El lenguaje Lne:
Está formado por todas aquellas codificaciones de máquinas de Turing que aceptan la cadena vacía.
Está formado por todas aquellas codificaciones de máquinas de Turing que no aceptan ninguna cadena
de entrada.
Está formado por todas aquellas codificaciones de máquinas de Turing que al menos aceptan una
cadena de entrada.
- 8. Multiple Choice
El algoritmo Quicksort...
Tiene aleatoriedad.
No tiene aleatoriedad.
Es un algoritmo que no puede ser reconocido por ninguna MT.
- Answer choicesTagsAnswer choicesTags