QUIZ DE TEORIA
Cualquier problema que pueda ser resuelto en una computadora también puede ser resuelto en una Máquina de Turing.
Verdadero
Falso
¿Qué estructuras de datos o conceptos se asocian con las gramáticas independientes del contexto?
Pilas
Árboles de derivación.
Cadenas baleiras (λ, ε).
Funciones de transición estendida.
En la jerarquía de Chomsky, ¿a qué tipo pertenecen las gramáticas independientes del contexto?
Tipo 0
Tipo 1
Tipo 2
Tipo 3
Verdadero o Falso: Los Autómatas con Pila pueden reconocer algunos lenguajes que no son regulares.
Verdadero
Falso
Verdadero o Falso: Una gramática independiente del contexto para el lenguaje de palíndromos necesita al menos dos variables.
Verdadero
Falso
Verdadero o Falso: Las Máquinas de Turing no son capaces de resolver todos los problemas de decisión.
Verdadero
Falso
Verdadero o Falso: Una Máquina de Turing con opción de no-movimiento es menos potente que una Máquina de Turing estándar.
Verdadero
Falso
Verdadero o Falso: En la teoría de la computabilidad, todas las Máquinas de Turing son equivalentes desde el punto de vista de la decidibilidad.
Verdadero
Falso
¿Cuál de las siguientes afirmaciones sobre los autómatas finitos es correcta?
Son capaces de reconocer cualquier tipo de lenguaje, incluyendo los sensibles al contexto.
No pueden reconocer lenguajes que contengan una cantidad arbitraria de caracteres repetidos.
Pueden tener un número infinito de estados.
Todos los autómatas finitos son no deterministas.
¿Qué estructura de datos se utiliza comúnmente en el análisis de gramáticas independientes del contexto?
Pilas
Colas
Árboles
Grafos
Una gramática regular es aquella cuyas producciones son:
Siempre lineales por la derecha.
Siempre lineales por la izquierda.
Pueden ser lineales por la derecha o por la izquierda.
No lineales ni por la derecha ni por la izquierda.
¿Qué es un ALA (Autómata Linealmente Acotado)?
Una Máquina de Turing con cinta infinita en ambas direcciones.
Un autómata finito que acepta lenguajes regulares.
Un tipo de Máquina de Turing que opera en una cinta de tamaño limitado.
Un autómata con pila que puede utilizar una cantidad infinita de memoria.
¿Qué representa una Máquina de Turing Universal (MTU)?
Una MT diseñada para resolver un único tipo de problema.
Una MT que es capaz de simular cualquier otra MT dada una descripción adecuada de esta.
Una MT que se detiene para todos los problemas decidibles.
Una MT con capacidad de almacenamiento infinito.
En la jerarquía de Chomsky, ¿qué tipo de gramáticas son las menos restrictivas?
Tipo 0
Tipo 1
Tipo 2
Tipo 3
¿Qué tipo de lenguaje es reconocido por los autómatas finitos?
Lenguajes regulares
Lenguajes independientes del contexto
Lenguajes dependientes del contexto
Lenguajes recursivamente enumerables
¿Qué determina la complejidad de un algoritmo en teoría de la computación?
La cantidad de espacio en la cinta de una Máquina de Turing que el algoritmo utiliza.
La longitud del código fuente del algoritmo.
La cantidad de tiempo y memoria que el algoritmo requiere para una entrada de tamaño n.
La dificultad del problema que el algoritmo intenta resolver.
¿Cuál es la finalidad del lema del bombeo en teoría de autómatas?
Probar que un lenguaje es regular.
Demostrar que un lenguaje es recursivo.
Proporcionar una técnica para simplificar las expresiones regulares.
Establecer condiciones que deben cumplir los lenguajes regulares e independientes del contexto.
¿Cuál de las siguientes opciones es una característica de los autómatas con pila?
Pueden reconocer cualquier lenguaje recursivamente enumerable.
No pueden utilizar memoria adicional aparte de su estructura de pila.
Utilizan una pila para almacenar una cantidad infinita de información.
Son capaces de reconocer lenguajes sensibles al contexto sin restricciones.
¿Qué es una función Turing-computable?
Una función que puede ser calculada en tiempo polinómico.
Una función que puede ser computada por una Máquina de Turing.
Una función que siempre produce una salida en un número finito de pasos.
Una función que no puede ser resuelta por una Máquina de Turing.
¿Qué establece la tesis de Church-Turing?
Que las Máquinas de Turing son el único modelo de computación posible.
Que todo problema computacional puede ser resuelto eficientemente.
Que cualquier modelo de computación efectivo puede ser simulado por una Máquina de Turing.
Que los problemas indecidibles no pueden ser resueltos por las Máquinas de Turing.
¿Qué es NP-completo en el contexto de la complejidad computacional?
Una clase de problemas que pueden ser resueltos en tiempo no polinómico.
Una clase de problemas que solo pueden ser resueltos por una Máquina de Turing no determinista.
Un problema que pertenece a NP y todos los problemas en NP pueden ser reducidos a él en tiempo polinómico.
Un problema que puede ser verificado en tiempo polinómico, pero no necesariamente resuelto en ese tiempo.
¿Qué se utiliza para probar que un lenguaje no es independiente del contexto?
El lema del bombeo para lenguajes regulares.
El lema del bombeo para lenguajes independientes del contexto.
La tesis de Church-Turing.
La teoría de autómatas finitos.
¿Cuál es la relación entre los autómatas finitos y las expresiones regulares?
Los autómatas finitos son una subclase de las expresiones regulares.
Las expresiones regulares pueden generar lenguajes que los autómatas finitos no pueden reconocer.
Los autómatas finitos y las expresiones regulares son equivalentes en cuanto a los lenguajes que pueden reconocer o generar.
Las expresiones regulares son una herramienta para optimizar autómatas finitos.
{"name":"QUIZ DE TEORIA", "url":"https://www.quiz-maker.com/QFGA51YK7","txt":"Cualquier problema que pueda ser resuelto en una computadora también puede ser resuelto en una Máquina de Turing., Una Máquina de Turing puede tener un número infinito de celdas en su cinta., Los Autómatas Linealmente Acotados son menos potentes que las Máquinas de Turing.","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}
