Javier blue
Quiz by , created more than 1 year ago

cosas

44
0
0
No tags specified
Javier blue
Created by Javier blue almost 4 years ago
Close

cosas

Question 1 of 33

1

Es posible que una Máquina de Turing tenga un único estado:

Select one of the following:

  • Verdadero

  • Falso

Explanation

Question 2 of 33

1

Todo lenguaje recursivamente enumerable:
Seleccione una:

Select one of the following:

  • a. Es dependiente del contexto

  • b. Es recursivo

  • c. Ninguno de los anteriores

  • d. Es regular

  • e. Es independiente del contexto

Explanation

Question 3 of 33

1

Si L1 y L2 son lenguajes recursivamente enumerables, entonces L1 U L2, también los es:

Select one of the following:

  • Verdadero

  • Falso

Explanation

Question 4 of 33

1

Una Máquina de Turing para cuando su cabeza de lectura alcanza el final de la cadena que se le suministra como entrada.

Select one of the following:

  • Verdadero

  • Falso

Explanation

Question 5 of 33

1

Si un lenguaje es independiente del contexto …
Seleccione una o más de una:

Select one or more of the following:

  • a. Existe una Máquina de Turing que lo reconoce

  • b. Existe una gramática regular que lo genera

  • c. Existe un DFA mínimo que lo reconoce

  • d. Existe una Máquina de Turing, que para ante cualquier cadena de entrada, que lo reconoce

  • e. Existe una gramática independiente del contexto que lo genera

Explanation

Question 6 of 33

1

Indicar cuáles de las siguientes cadenas binarias pueden ser una codificación de una máquina de Turing:
Seleccione una o más de una:

Select one or more of the following:

  • a.01110111110111111101110110101101110110111110

  • b. 0111011111011111110111011010110111011010

  • c. 0101101110110101011011011010

  • d. 01110111110111111100111011010110111011010

Explanation

Question 7 of 33

1

Dados un lenguaje y su complementario, indicar las posibilidades que son posibles:
Seleccione una o más de una:

Select one or more of the following:

  • a. Que ninguno de los dos sea recursivamente enumerable

  • b. Que uno sea recursivo y el otro recursivamente enumerable

  • c. Que ambos sean recursivos

  • d. Que ambos sean independientes del contexto

  • e. Que uno sea regular y el otro recursivamente enumerable

Explanation

Question 8 of 33

1

Si un lenguaje L es independiente del contexto, entonces su complementario es recursivo:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 9 of 33

1

Una máquina de Turing acepta una cadena ...
Seleccione una o más de una:

Select one or more of the following:

  • a. Cuando se queda parada

  • b. Cuando se encuentra parada en un estado de aceptación

  • c. Cuando después de leer todos los símbolos de la cadena, se encuentra en un estado de aceptación

  • d. Cuando ha leído todos los símbolos de la cadena de entrada

  • e. Cuando al leer la cadena, la máquina nunca para

Explanation

Question 10 of 33

1

Si L, Σ* y -L son recursivamente enumerables, entonces ambos son recursivos:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 11 of 33

1

Si un lenguaje es recursivamente enumerable ...
Seleccione una o más de una:

Select one or more of the following:

  • a. Existe una Máquina de Turing, que para ante cualquier cadena de entrada, que lo reconoce

  • b. Existe una Máquina de Turing que lo reconoce

  • c. Existe una gramática regular que lo genera

  • d. Existe una gramática independiente del contexto que lo genera

  • e. Existe un DFA mínimo que lo reconoce

Explanation

Question 12 of 33

1

El complementario de un lenguaje recursivamente enumerable
Seleccione una:

Select one or more of the following:

  • a. Es recursivamente enumerable

  • b. Es regular

  • c. Ninguno de los anteriores

  • d. Es independiente del contexto

  • e. Es dependiente del contexto

  • f. Es recursivo

Explanation

Question 13 of 33

1

Todo lenguaje regular
Seleccione una o más de una:

Select one or more of the following:

  • a. Es independiente del contexto

  • b. Es recursivo

  • c. Es recursivamente enumerable

  • d. Es dependiente del contexto

Explanation

Question 14 of 33

1

Los lenguajes que las máquinas de Turing aceptan ...
Seleccione una:

Select one or more of the following:

  • a. Son infinitos

  • b. Son regulares

  • c. Son recursivos

  • d. No son recursivamente enumerables

  • e. Son finitos

  • f. Son recursivamente enumerables

Explanation

Question 15 of 33

1

L es un lenguaje independiente del contexto si y sólo si L es un lenguaje recursivo:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 16 of 33

1

Todo lenguaje recursivo
Seleccione una:

Select one or more of the following:

  • a. Es dependiente del contexto

  • b. Es recursivamente enumerable

  • c. Es regular

  • d. Es independiente del contexto

Explanation

Question 17 of 33

1

Los lenguajes recursivamente enumerables son cerrados respecto a la operación de …
Seleccione una o más de una:

Select one or more of the following:

  • a. Intersección

  • b. Unión

  • c. Complementación

Explanation

Question 18 of 33

1

Si un lenguaje está especificado mediante una expresión regular, entonces es recursivo:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 19 of 33

1

El complementario de un lenguaje recursivamente:
Seleccione una:

Select one or more of the following:

  • a. Es regular

  • b. Es dependiente del contexto

  • c. Es independiente del contexto

  • d. Es recursivamente enumerable

  • e. Es recursivo

Explanation

Question 20 of 33

1

Los lenguajes recursivos son cerrados respecto a la operación de …
Seleccione una o más de una:

Select one or more of the following:

  • a. Intersección

  • b. Unión

  • c. Complementación

Explanation

Question 21 of 33

1

Una máquina de Turing puede ...
Seleccione una o más de una:

Select one or more of the following:

  • a. Reconocer un lenguaje independiente del contexto

  • b. Invertir los símbolos (calcular la cadena inversa) de una cadena que se le dé como entrada

  • c. Transformar una cadena que toma como entrada, en otra cadena

  • d. Aceptar o rechazar cadenas de un lenguaje, siempre que éste sea recursivamente enumerable
    enumerable

  • e. Aceptar las cadenas de un lenguaje que no es recursivamente enumerable

  • f. Calcular el máximo entre dos números

Explanation

Question 22 of 33

1

Cualquier sublenguaje de un lenguaje regular, es regular Seleccione una:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 23 of 33

1

Una Máquina de Turing (MT) no determinista con k cabezas de lectura/escritura puedereconocer más lenguajes que una MT con k cintas. Seleccione una:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 24 of 33

1

Si L es recursivamente enumerable, entonces Σ* -L también lo es:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 25 of 33

1

La capacidad de cómputo de una máquina de Turing no determinista ...
Seleccione una o más de una:

Select one or more of the following:

  • a. Es igual que la de una máquina de Turing multicinta

  • b. Es mayor que la de un DFA

  • c. Es mayor que la de una máquina de Turing determinista

  • d. Es menor que la de una máquina de Turing con cinta multidimensional

Explanation

Question 26 of 33

1

Una Máquina de Turing para cuando su cabeza de lectura alcanza el final de la cadena que se le suministra como entrada.
Seleccione una:

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Question 27 of 33

1

¿Cuáles de los siguientes lenguajes podrían ser aceptados por máquinas de Turing?
Seleccione una o más de una:

Select one or more of the following:

  • a. Los lenguajes recursivamente enumerables

  • b. Los lenguajes recursivos

  • c. Los lenguajes naturales

  • d. Cualquier lenguaje infinito

  • e. Los lenguajes regulares

  • f. Cualquier lenguaje finito

Explanation

Question 28 of 33

1

Una máquina de Turing: Seleccione una o más de una:

Select one or more of the following:

  • a. Es capaz de aceptar una cadena de entrada de longitud infinita

  • b. Tiene al menos una cinta (de longitud infinita)

  • c. Tiene al menos un estado

  • d. Puede tener un alfabeto para la cinta que coincida exactamente con el alfabeto de entrada

  • e. Tiene un único estado de arranque

  • f. Tiene al menos una transición para cada símbolo de entrada

Explanation

Question 29 of 33

1

¿Cuáles de las siguientes afirmaciones son ciertas? Seleccione una o más de una:

Select one or more of the following:

  • a. Los lenguajes recursivos son cerrados respecto a la operación de unión

  • b. Los lenguajes recursivamente enumerables son cerrados respecto a la operación de complementación

  • c. Los lenguajes recursivos son cerrados respecto a la operación de complementación

  • d. Los lenguajes recursivos son cerrados respecto a la operación de intersección

  • e. Los lenguajes recursivamente enumerables son cerrados respecto a la operación de unión

Explanation

Question 30 of 33

1

Dados un lenguaje y su complementario, indicar las posibilidades que son posibles: Seleccione una o más de una:

Select one or more of the following:

  • a. Que uno sea regular y el otro recursivamente enumerable, pero no recursivo

  • b. Que ambos sean independientes del contexto

  • c. Que ninguno de los dos sea recursivamente enumerable

  • d. Que uno sea recursivo y el otro recursivamente enumerable, pero no recursivo

  • e. Que ambos sean recursivos

Explanation

Question 31 of 33

1

La capacidad de cómputo de una máquina de Turing no determinista ...
Seleccione una o más de una:

Select one or more of the following:

  • a. Es igual que la de una máquina de Turing multi-cinta

  • b. Es menor que la de una máquina de Turing multi-pista

  • c. Es mayor que la de un NFA

  • d. Es menor que la de una máquina de Turing con cinta multi-dimensional

  • e. Es mayor que la de un DFA

  • f. Es mayor que la de una máquina de Turing determinista

Explanation

Question 32 of 33

1

¿Cuáles de las siguientes son modificaciones de la máquina de Turing estándar?Seleccione una o más de una:

Select one or more of the following:

  • a. Máquinas de Turing multi-cinta

  • b. Máquinas de Turing no deterministas

  • c. Máquinas de Turing con cinta finita

  • d. Máquinas de Turing multi-pista

  • e. Máquinas de Turing unimodales.

  • f. Máquinas de Turing con posibilidad de no moverse

Explanation

Question 33 of 33

1

Σ* es siempre un conjunto infinito

Select one or more of the following:

  • Verdadero

  • Falso

Explanation

Previous
Next