CyC Deusto E3#0

¿Se puede afirmar que λ pertenece a L+?. Solo si L contiene a λ. De ninguna manera. Solo si L no contiene a λ.

¿Se puede afirmar que λ no pertenece a L*?. Solo si L contiene a λ. De ninguna manera. Solo si L no contiene a λ.

Dadas las siguientes definiciones auxiliares dnc = 1|2|3|...|9 dig = 0|1|2|...|9 Y el siguiente autómata se tendrá que: d*(q0, 602s743) = {q1,q2}. d*(q0, 602s743) = {q2 }. d*(q0, 602s743) = { }.

Los autómatas finitos no deterministas (AFND) reconocen: Los mismos lenguajes que los AFD (autómatas finitos deterministas). Más lenguajes que los AFD (autómatas finitos deterministas). Menos lenguajes que los AFD (autómatas finitos deterministas).

Los autómatas con pila deterministas reconocen: Los mismos lenguajes que los AFD. Más lenguajes que los AFD. Menos lenguajes que los AFD.

Los autómatas con pila no deterministas reconocen: Los mismos lenguajes que los autómatas con pila deterministas. Más lenguajes que los autómatas con pila deterministas. Menos lenguajes que los autómatas con pila deterministas.

Al demostrar (primera postcondición de Kleene) que toda expresión regular puede transformarse en un autómata finito equivalente, se garantiza: ΔER ⊆ ΔAF. ΔER ⊇ ΔAF. ΔER = ΔAF.

Al demostrar (segunda postcondición del teorema de Kleene) que para todo autómata finito puede encontrarse una expresión regular equivalente, se garantiza: ΔER ⊆ ΔAF. ΔER ⊇ ΔAF. ΔER = ΔAF.

El lenguaje {aⁿ bⁿ cⁿ |n>0} es importante porque: No es independiente del contexto. Puede ser expresado con fórmula, pero no con gramática de tipo 0. Puede ser reconocido con un APD, pero no con un APND.

El lenguaje {aⁿ bⁿ |n>0} es importante porque: No es independiente del contexto. Es independiente del contexto y regular. Es independiente del contexto, pero no regular.

La siguiente definición recursiva ¿Qué lenguaje representa? 1- a es x 2- si a es x entonces aa es x 3- la definición es completa. {aᵏ|K=2ⁿ, n>=0}. {aᵏ|K=2ⁿ, n>0}. {aᵏ|K=2n, n>=0}.

Uno de los primeros problemas matemáticos de los cuales se supo que estaban en NP fue: El problema de la parada de la Máquina de Turing. El problema de la correspondencia de Post. Problema del viajante.

La jerarquía de clases de complejidad. O(N) ⊂ O(N²) ⊂ O(logN) ⊂ O(NlogN) ⊂ O(2ⁿ). O(logN) ⊂ O(N) ⊂ O(NlogN) ⊂ O(N²) ⊂ O(2ⁿ). O(logN) ⊂ O(NlogN) ⊂ O(N) ⊂ O(2ⁿ) ⊂ O(N²).

La máquina de Turing universal Muniv funciona: Para con algunas cadenas de entrada. Para con todas las cadenas de entrada. No puede existir (problema de la parada).

La máquina de Turing universal es: Un mecanismo capaz de procesar cualquier algoritmo. Una máquina capaz de reconocer algunas cadenas. Un mecanismo capaz de reconocer algunos algoritmos simples.

¿Cuál de las siguientes combinaciones es solución al sistema de Post que aparece a continuación?. 2, 1, 3, 3. 1, 3, 2, 1. 3, 1, 3, 2.

El problema P = NP significa: No se sabe si hay algún problema que esté en NP y no en P, ni lo contrario. No se sabe si hay algún problema que esté en P y no en NP, ni lo contrario. Todo lo que se puede hacer con tasa polinómica con una máquina de Turing no determinista (NP) se puede hacer con una determinista (P).

El problema del viajante: Está en la clase NP y no en P, que es lo mismo que decir que de momento no se conoce ningún algoritmo eficiente. Está en la clase P y no en NP. No se sabe si está en la clase NP.

Si la máquina modular SD se aplica a la cadena ΔaaaΔaa(a)aa ¿Cuál es la configuración que resulta?. ΔaaaΔa(a)aa. ΔaaaΔaa(a)a. Δ(a)aaΔaaaa.

El módulo DΔ. Es posible que produzca bucle sin fin. Es imposible que produzca bucle sin fin. Solo puede usarse para máquinas generadoras.

Se ha demostrado que las gramáticas de Chomsky son equivalentes a las máquinas de Turing, ello: Demuestra la tesis Church-Turing. Apoya la tesis Church-Turing. Pone en duda la tesis Church-Turing.

Para demostrar que todo lenguaje aceptado por una MT no determinista puede ser aceptado por una MT determinista, hace falta: Una máquina de 3 cintas en la que se van aplicando todos los caminos. Una máquina de 2 cintas en la que se van aplicando todos los caminos. Una máquina de 3 cintas en la que se aplican algunos caminos.

El módulo DNOΔ. Es posible que produzca bucle sin fin. Es imposible que produzca bucle sin fin. Solo puede usarse para máquinas generadoras.

Se considera que no pueden ser eficientes los algoritmos: Exponencial. Constante. Otros.

Dado el alfabeto T ({a, b}*). T* no es un lenguaje. cadena vacia no pertenece a T*. T* no está vacio.

Tengo un lenguaje, lo meto en una MT y para en una a: L(M): Conjunto de cadenas que desembocan en el estado de parada (qh), por lo tanto, lenguajes aceptados por M. R(M): Conjuntos de cadenas que llevan a la máquina a situación de error, bien por rebasar el estado izquierdo o bien por estar en un estado del que no existe transición posible. B(M): Conjunto de cadenas en que la máquina no para nunca.

El arte esta en que. Una cosa no es lo que es, sino su representación. Se debe copiar la realidad física de la manera más fiel posible. La imagen de un objeto es exactamente el objeto mismo.

La tesis de Church-Turing implica que. Cualquier sistema de Post tiene solucion. Existen algoritmos que no pueden ser ejecutados por una máquina de Turing. Todo problema matemático puede ser resuelto por un ordenador.

En POSIX, [^<&>\n] significa: Una linea con & como unico caracter y el cambio de linea siguiente. Cualquier caracter menos <, &, > y el cambio de linea. Cadenas que empiezan por < y terminan por > entre el comienzo y el final de linea.

Si T es un alfabeto: T* no es un lenguaje. T* no contiene λ. T* no es vacio.

La expresion regular b*(a c b*)* es equivalente a: (b* a c)* b*. b*(a c b*)+ | λ⊂. (b*a)* (cb*)*.

Si Ai es el conjunto de lenguajes generado por las gramáticas independientes del contexto Aapd es el conjunto de lenguajes reconocidos por autómatas con pila deterministas, lo correcto es: Ai ⊂ AAPD. AI ⊃ AAPD. AI = AAPD.

En la siguiente máquina M: bababbb ∈ R(M). bababbb ∈ B(M). bababbb ∈ L(M).

La tesis de Church-Turing sostiene que: Las gramáticas de Chomsky son equivalentes a las máquinas de Turing. La máquina de Turing es el modelo de cálculo más general que existe. Los algoritmos con una tasa exponencial son eficientes.

Si ΛTd es el conjunto de lenguajes Turing-decidibles y Λ0 es el conjunto de lenguajes generados por gramáticas tipo 0 de Chomsky, lo correcto es: A. B. C.

Un argumento a favor de la tesis de Church-Turing es que: Nadie ha encontrado un algoritmo eficiente para el problema del viajante. La máquina de Turing no determinista no se puede simular con una máquina de Turing determinista. Todos los lenguajes de programación de propósito general tienen similar capacidad de solución de problemas.

El módulo Da aplicado a Δaba(a): No hace nada, no se mueve. No acaba nunca. Produce Δabaa(Δ).

El lenguaje L = { ω = ωⁿ | ω ∈ {a, b}*}. Puede ser reconocido con un autómata con pila no determinista, pero no con un autómata con pila determinista. Puede ser expresado con una fórmula, pero no con una gramática de tipo 2. Es dependiente del contexto pero no terminal.

En la siguiente máquina de Turing M: bbbb∈L(M). bbbb∈R(M). bbbb∈B(M).

En una maquina de Turing dedicada al calculo de una fincion de dos argumentos, para calcular el resultado de f(abc, 111), la configuracion inicial ha de ser: Δ(a)bc111. Δ(a)bcΔ111. Δabc(Δ)111.

Indica la configuración que resulta si la máquina modular Si se aplica a la configuracion: Δa(a)aaΔaaaa. Δa(a)aΔaaaa. Δa(a)aΔΔaaaa. ΔΔ(a)aaΔaaaa.

El módulo Ia (siendo a distinto de Δ). no tiene peligro, es seguro. tiene peligro de bucle sin fin. tiene peligro de borde izquierdo.

Indica la configuracion que resulta si el módulo D*Δ se aplica a : Δ7429(Δ)kjk. Δ7429(Δ)kjk. Δ7429Δkjk(Δ). (Δ)7429Δkjk.

Si L es Turing-aceptable, pero no Turing-decidible, entonces: ^L(Complementario de L) es Turing-decidible. ^L(Complementario de L) es Turing-aceptable, pero no Turing-decidible. ^L(Complementario de L) no es Turing-aceptable.

Es imposible construir: la maquina de Turing universal Muniv. la maquina de Turing universal Duniv que pare con todas las cadenas de entrada. la maquina de Turing no determinista.

La tesis de Church-Turing sostiene que el modelo de computación más general que existe es: la gramática de tipo 1. el autómata de varias cintas no determinista. el cálculo lambda.

El problema de P-NP significa que no se sabe: A. B. C.

Si T es un alfabeto: T* no es un lenguaje. T* no contiene λ. T* no es vacio.

Por mera lógica, a partir de la definición de Λafd ( lenguajes reconocidos por automatas finitos deterministas) y Λafn (lenguajes reonocidos por automatas finitos no deterministas), solo uno de los siguientes casos es posible. A. B. C.

Si Λapd es el conjunto de lenguajes reconocidos por automatas con pila deterministas, Λapn es el conjunto de lenguajes reconocidos por autómatas con pila no deterministas y Λafn es el conjunto de lenguajes reconocidos por autómatas finitos no deterministas, lo correcto es: Λ2(Gramaticas de tipo 2) = Λapd. Λ2(Gramaticas de tipo 2) = Λafn. Λ2(Gramaticas de tipo 2) = Λapn.

En la siguiente máquina de Turing M: bababbba ∈ L(M). bababbb ∈ B(M). babbbaabb ∈ R(M).

El módulo Da̅ aplicado a la configuración Δaba(a): no acaba nunca. produce la configuración Δabaa(Δ). produce la configuración Δ(a)baa.

El módulo Da aplicado a la configuración Δaba(a): no acaba nunca. produce la configuración Δabaa(Δ). produce la configuración Δaba(a) (es decir, no hace realmente nada).

Por definición, un lenguaje es Turing-aceptable: si tiene una máquina de Turing. si tiene una máquina de Turing modular. si tiene una máquina de Turing que para con todas las cadenas de entrada.

Si ΛTa es el conjunto de lenguajes Turing-aceptables y Λ0 es el conjunto de lenguajes generados por gramáticas de tipo 0 (cero) de Chomsky, lo correcto es: A. B. C.

Se puede afirmar que L*: contiene λ o no contiene λ dependiendo de L. no contiene λ. contiene λ.

Si ΛER es el conjunto de lenguajes descritos por expresiones regulares y ΛAF el conjunto de lenguajes aceptados por autómatas finitos, lo correcto es: A. B. C.

Si Λ2 es el conjunto de lenguajes generados por gramáticas de tipo 2 y ΛPD es el conjunto de lenguajes reconocidos por autómatas con pila deterministas, lo correcto es: Λ2⊂ΛAPD. ΛAPD⊂Λ2. Λ2=ΛAPD.

Si ΛAPD es el conjunto de lenguajes reconocidos por autómatas con pila deterministas y ΛAPN el de lenguajes reconocidos por autómatas con pila no deterministas, lo correcto es: A. B. C.

El lenguaje { a^n b^n c^n | n > 0} tiene una gramática: regular. independiente del contexto. dependiente del contexto.

El lenguaje Luniv aceptado por la máquina de Turing universal Muniv es: Turing-aceptable, pero no Turing-decidible. Turing-decidible, pero no Turing-aceptable. ni Turing-decidible ni Turing-aceptable.

El lenguaje L̅u̅n̅i̅v̅, complementario del lenguaje Luniv aceptado por la máquina de Turing universal Muniv, es: Turing-aceptable, pero no Turing-decidible. Turing-decidible, pero no Turing-aceptable. ni Turing-decidible ni Turing-aceptable.

Una máquina de Turing, dedicada al cálculo de una función f, con la cadena de entrada ω entra en un bucle sin fin; entonces el resultado f(ω): es 0. es infinito. no está definido.

Una máquina de Turing, dedicada al cálculo de una función f, con la cadena de entrada ω intenta rebasar el borde izquierdo; entonces el resultado f(ω): es 0. es el mismo que si la máquina tuviera un bucle sin fin. depende de lo que haya en la cinta.

En una máquina de Turing, dedicada al cálculo de la función f: T*xNxT*, para calcular el resultado de f(abc, 111, xy), la configuración inicial ha de ser: ΔabcΔ111Δx(y). Δ(a)bcΔ111Δxy. Δabc•111=xy.

En una máquina de Turing, dedicada al cálculo de la función f: T*xNxT*, para calcular el resultado de f(abc, 111, xy)=a1x, la configuración inicial ha de ser: Δ(a)1x. Δa1(x). Δa(•)1=x.

Indica la configuración que resulta si el módulo DΔ* se aplica a Δ7429(Δ)kjk. Δ7429(Δ)kjk. Δ7429Δkjk(Δ). (Δ)7429Δkjk.

La máquina de Turing universal Muniv: para con algunas cadenas de entrada. para con todas las cadenas de entrada. no puede existir (problema de la parada).

Para demostrar que todo lenguaje aceptado por una máquina de Turing no determinista puede ser aceptado con una máquina de Turing determinista, se simula la máquina no determinista con: una máquina generadora, que enumera una por una todas las cadenas de T*: si se genera alguna vez la cadena de entrada, esta es aceptada. una máquina que realiza un proceso de backtracking: si siguiendo un camino no se llega al estado de parada, se vuelve atrás para comenzar por otro camino, y así sucesivamente. una máquina de tres cintas, en la que se van aplicando todos los caminos con una transición, luego con dos, luego con tres, etc., hasta que se llega a aceptar la cadena, si esta es del lenguaje.

Si ΛTD es el conjunto de lenguajes Turing-decidibles y Λ0 es el conjunto de lenguajes generados por gramáticas tipo 0 (cero) de Chomsky, lo correcto es: A. B. C.

Se ha demostrado que las gramáticas de Chomsky son equivalentes a las máquinas de Turing. Ello: demuestra la tesis de Church-Turing. apoya la tesis de Church-Turing. pone en duda la tesis de Church-Turing.

El problema del viajante (TSP, traveling salesman problem): está en la clase NP y no se sabe si está en P, que es lo mismo que decir que de momento no se conoce algoritmo determinista eficiente. está en la clase P y no se sabe si está en NP, que es lo mismo que decir que tiene un algoritmo no determinista eficiente. no se sabe si está en la clase P o en la clase NP, ya que todavía no se sabe si P = NP.

En el problema P=NP, lo que se sabe con total seguridad es que: P ⊆ NP. NP ⊆ P. P = NP.

La expresión regular (ab)*a equivale a: a(a|b)*a. a(ab)*. a(ba)*.

La expresión regular (aba)*a equivale a. a(a|b)*a. a(bb|a)*. a(baa)*.

La expresión regular a(b|ab)* hará la cadena. abaababb. aabbbbbab. abababababa.

Dada la definición auxiliar de dígito hexadecimal h=... y la expresión regular r3=h+(h*sh+)*h+. Todas las cadenas tienen un número par de dígitos hexadecimales. Todas las cadenas tienen cualquier número de dígitos hexadecimales. Las cadenas tienen dos o más dígitos hexadecimales.

El siguiente autómata finito equivale a. a(ba)*. (ab)*ab. a*(ba)*b*.

En el siguiente autómata finito con transiciones por la cadena vacía se cumple: d*(q0, aaa) = {q0,q1,q3}. d*(q0, aaa) = { }. d*(q0, aaa) = {q0,q1,q2,q3}.

El siguiente diagrama de estados: No puede llamarse autómata finito, ya que contiene transición por cadena vacía (λ). Es un autómata determinista. Es un autómata no determinista.

La gramática es de: S->AB AB->aBA aB->Ba A->bA|b. Tipo 0. Tipo 1. Tipo 2.

La gramática es de: S->AB AB->D aB->Ba A->bA|b. Tipo 0. Tipo 1. Tipo 2.

En una máquina de Turing, dedicada al cálculo de la función f: T*xNxT*, para calcular el resultado de f(abc, 111, xy)=a1x, la configuración final ha de ser: Δ(a)1x. Δa1(x). Δa(•)1=x.