CyC Deusto

Dado: ω=ababbb, r=(ab*)*, F={(abⁿ)ᵐ ∣ n≥0 ^ m≥0} Se puede afirmar que: ω∈L(r)∧ω∈L(F). ω∈L(r)∧ω∉L(F). ω∉L(r)∧ω∉L(F).

Dado: ω=abbabb, r=(ab*)*, F={(abⁿ)ᵐ ∣ n≥0 ^ m≥0} Se puede afirmar que: ω∈L(r)∧ω∈L(F). ω∈L(r)∧ω∉ L(F). ω∉L(r)∧ω∉L(F).

Dado: r=(b*a)*, F={(bⁿa)ᵐ ∣n≥0∧m>0} Se puede afirmar que: r y F representan el mismo lenguaje. r y F no representan el mismo lenguaje. r y F no tienen cadenas en común.

La expresión regular (a; )* a es equivalente a: a (; | a)*. a (; a)*. a (a ;)*.

La expresion regular a ( b | a a)* incluye, entre otras, la cadena: aaaaabaabbb. aaaabbaabbb. aaabababababb.

La especificación "cadenas con un número impar de aes" queda mejor reflejada por la expresión regular: b* a b* ( a b* a b* )*. ( a | b)* a a a (a | b)*. ( a a | b )* a (a a | b )*.

El siguiente autómata finito reconoce el mismo lenguaje que: a* ( b b a* )*. ( a | b a* b )*. a* (a* b | b* a )* a*.

El siguiente autómata finito reconoce, entre otras, la cadena: bbabbabbabb. aabaabaabaa. ∅.

Los automatas finitos no deterministas reconocen: Los mismos lenguajes que las expresiones regulares. Menos lenguajes que las expresiones regulares. Más lenguajes que las expresiones regulares.

En POSIX, para expresar "cualquier carácter menos el espacio, tabulador y cambio de linea" hay que escribir: ( | \t | \n)?. [ ^ | \t | \n]. . | [ \t \n].

En POSIX, [1023]: representa un digito entre 0 y 3. representa la cadena 1023. es un error, falta -.

En POSIX, el uso de ? es para. a? = a | λ. a? es cualquier caracter menos a. nada en particular, no tiene significado propio.

Dadas las definiciones auxiliares: s = [ \t \n] ld = {l}{d}* y las transiciones: es determinista. es no determinista. es un error mayúsculo.

El siguiente automata finito reconoce: cadenas con un nº impar de bes. cadenas que no tienen dos bes consecutivas. cadenas con aes intercaladas entre bes.

Dadas las siguientes definiciones auxiliares: l = [a-z A-Z] d = [0-9] c = / / . * el siguiente automata: es determinista. es no determinista. es un error mayúsculo.

¿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 λ.

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={0 | ... | 9 | a... | f | A... | F} 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*.

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) = { }.

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.

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}.

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

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

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.

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.

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 siguiente automata finito equivale a: a(ba)*. (ab)*ab. a*(ba)*b*.