CyC - test final y parcial

Dado: w = ababbb r = (ab*)* F = { (abn)m | n>= 0 ^ m>=0} se puede afirmar que: w∈L(r) ^ w∈L(F). w∈L(r) ^ w∉L(F). w∉L(r) ^ w∈L(F).

Dado: w = abbabb r = (ab*)* F = { (abn)m | n>= 0 ^ m>=0} se puede afirmar que: w∈L(r) ^ w∈L(F). w∈L(r) ^ w∉L(F). w∉L(r) ^ w∈L(F).

Dado: r=(b*a)+ F = { (b^n a)^m | 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 expresión 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* ( ab* ab* )*. ( 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 autómatas 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, el tabulador y el cambio de línea" hay que escribir: ( | \t | \n)?. [^ \t \n ]. . | [ \t \n ].

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

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

Dadas kas definiciones auxiliares: s = [ \t \n ] id = {l} {d}* y las transiciones, el autómata finito que lo contenga: es determinista. es no determinista. es un error mayúsculo.

El siguiente autómata finito reconoce: cadenas con un n* impar de bes. cadenas que no tienen dos bes consecutivas. cadenas con aes intercaladas entre las bes.

Dadas las siguientes definiciones auxiliares: l = [a-zA-Z_] d = [ 0-9 ] c = / / . * el siguiente autómata: es determinista. es no determinista. es un error mayúsculo.

Se puede afirmar que λ∉L* ?. Si, para todo L. Solo si L no contiene λ. De ninguna manera.

Los autómatas finitos no deterministas reconocen: más lenguajes que los autómatas con pila deterministas. los mismos lenguajes que los autómatas con pila deterministas. menos lenguajes que los autómatas con pila deterministas.

El lenguaje Lpal = { w=wR | w∈{a,b}*} ha de ser recordado porque: 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.

El lenguaje { a^n b^n c^n | n>0 } es importante porque: puede ser reconocido con un autómata con pila determinista, pero no con un autómata con pila no determinista. no es independiente del contexto. puede ser expresado con una fórmula, pero no con una gramática de tipo cero.

Por definición, un lenguaje es Turing-decidible: 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.

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

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

El arte está en: unas palabras en inglés. unas palabras en francés. unas letras griegas.

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

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

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.

La jerarquía de clases de complejidad en la notación "o mayúscula" es: O(N) ⊆ O(N^2) ⊆ O(log N) ⊆ O(N log N) ⊆ O(2^N). O(log N) ⊆ O(N) ⊆ O(N log N) ⊆ O(N^2) ⊆ O(2^N). O(log N) ⊆ O(N log N) ⊆ O(N) ⊆ O(2^N) ⊆ O(N^2).

La N de NP es la inicial de: no determinista. no polinómico. no decidible.

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

El problema del viajante (TSP, traveling salesman problem): se puede resolver con un algoritmo determinista eficiente (por lo que está en P), pero los algoritmos no deterministas conocidos tienen tasa exponencial. se puede resolver con un algoritmo no determinista eficiente (por lo que está en NP), pero los algoritmos deterministas conocidos tienen tasa exponencial. no se sabe si está en la clase P o en la clase NP, ya que todavía no se sabe si P = NP.