8 questions
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.
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.
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).
El lenguaje universal...
Es recursivamente enumerable
Es recursivo
Es recursivamente enumerable y recursivo
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.
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.
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.
El algoritmo Quicksort...
Tiene aleatoriedad.
No tiene aleatoriedad.
Es un algoritmo que no puede ser reconocido por ninguna MT.