solysombra 2

Si A = {1, 2, 3} entonces: 2^A Ͻ Ø. 2^A Ͻ { A }. 2^A Ͻ A^2.

Si A = {1, 2} y B = {3, 4}, entonces R = {(1,4), (2,3)} : Es una función biyectiva de A a B. Es una función parcial de A a B. No es una aplicación de A a B.

La gramática ( { A }, { a }, { A -> Aa } , A ). Representa el lenguaje L = { }. Genera la derivación A -> Aa -> Aaa -> aaa. Es regular izquierda.

La gramática G = ( {S}, {b}, { SS -> bS }, S) es: De tipo 1 y no es de tipo 2. De tipo 0 y no es de tipo 1. De tipo 2 y no es de tipo 3.

Si A = {1, 2, 3} y R = {(1, 1), (2, 2)} entonces. R es una relación de equivalencia sobre A. R es una relación simétrica sobre A. R es una relación reflexiva sobre A.

Elija la opción correcta: ||N|| = 2 ^ ℵ0. ||R|| - ||N|| = 2 ^ ℵ0. ||Q|| = 2 ^ ℵ0.

La gramática ( { A }, { a }, { A -> Aa, A -> aA}, A). Genera la derivación A -> Aa -> aAa -> aaAaa. No es regular. Representa el lenguaje { ɛ }.

Sea Σ = {a, b, c}. Dado L = {w ϵ Σ* | aa no es subcadena de w }, una ER del mismo es: L = (b+c)* (a+ɛ) ( ( b+c) (a+ɛ) ) * (b+c)*. L = (b+c)* a ( (b+c) a )* (b+c)*. L = (b+c)* (a+ɛ) (b+c) (a+ɛ).

Dados A = {1, 2, 3}, B = {4} y R = {(1,4)}, se cumple que: R es un subconjunto de A x B. R es una relación binaria sobre A. R es una relación de equivalencia sobre A.

El cierre amplio de un conjunto para una operación. No incluye el conjunto vacío. No incluye el elemento neutro. Incluye su cierre estricto.

Marca la afirmación verdadera: x ≠ x^R e y ≠ y^R -> xy ≠ yx, x,y ϵ Σ*. (wx)^2 = w^2 x^2 , (para todo) x,y ϵ Σ*. (wx)^R = x^R w^R, (para todo) x,y ϵ Σ*.

Marca la afirmación falsa: ɛ ϵ L <-> L+ = L*. Ø { ɛ } = { ɛ } Ø = { ɛ }. Ø* = { ɛ } *.

El cierre simétrico de una relación R está definido como: R U R-1. R (intersección) R-1. R U I.

Para toda relación R, su cierre reflexivo es: R U R-1. R - 1. R U I.

Sea G = (N, T, P, S) con N = {A, B}, T = {0, 1}, P = { A -> 1100A | 0B | 0, B -> 0B|0}, S=A. ¿Cuál de los siguientes lenguajes es el lenguaje generado por G?. (1100)* 0. (1100)* 0 0*. (1100)* 00 0*.

Sea el monoide (N,+) y sea B (Contenido -> ) N. Si B = B + ^ ||B|| > 1, entonces: ||B|| = 2. ||B|| ϵ N. ||B|| = ℵ0.

El cardinal del conjunto potencia de un conjunto: Es cero si el conjunto es finito. Sólo es cero si el conjunto es el vacío. Nunca es cero.

Marca la afirmación verdadera: Todo lenguaje representable puede ser representado por una expresión regular. Todo lenguaje regular tiene al menos una expresión regular que lo representa. Existen gramáticas regulares que generan lenguajes que no son representables mediante expresiones regulares.

Una gramática generativa es. Una forma de representar lenguajes. Un subconjunto de L. REP. Un algoritmo conclusivo para reconocer lenguajes.

Marca la afirmación verdadera. La regla AB -> BA es sensible al contexto. La regla a -> aB es de tipo 1. La regla ABA -> BABA es sensible al contexto.

Sea R una relación sobre un conjunto A. R U R-1 es: La relación identidad. Ø. El cierre simétrico de R.

Sea G = (N, T, P, S) con N = {A, B}, T = {0, 1}, P = { A -> 1100ª | 0B | 0, B -> 0B| 0}, S = A. ¿De que tipos (0, 1, 2, RI, L, LI, LD) es la gramática?. Tipos 0, 1, 2, L y LD. Tipos 0, 1, 2, L y LI. Tipos 0, 1, 2, L, R.

Sean x e y dos cadenas, entonces x•y. Tiene longitud ≥ que la x. Es un conjunto infinito. Contiene |x| x |y| símbolos.

Los lenguajes de contexto libre son cerrados para las operaciones de: Unión, concatenación y complemento. Unión, concatenación, complemento, estrella de Kleene e intersección. Unión, concatenación y estrella de Kleene.

Elija la opción correcta: N^2 y N no son equipotenciales. N* y N son equipotenciales. Existen tantos vectores de tres naturales como números naturales.

Si R es una relación de equivalencia y D su conjunto diagonal entonces: || D || = 0. || D || ∉ N. || D || > 0.

La función Castor Afanoso es. Una aplicación biyectiva entre naturales. Parcialmente resoluble. Creciente ( m > n -> Σ(m) > Σ(n) ).

Del Teorema de Equivalencia podemos concluir que: Existe un programa universal. REC = F(T-WHILE). REC ⊆ F(WHILE).

El problema de la parada para programas con una entrada (dado por el predicado H1). Es parcialmente resoluble. ∈ TREC. Es no enumerable.

La función reemplazar del programa universal (reem) es: Una función parcial de 3 argumentos. Una función total. Una función inyectiva.

Si M = ( {s,f}, {a,b}, {a,b}, {(( s, aa, ε), (s,b)), (( s, ε, ε), (f, ε)), (( f, a, b), (f, ε))}, s,{f} ) entonces: L(M) = { w ∈ {a, b}* | w = a^3n con n∈ N }. L(M) = { www^R | w ∈ {a, b}*}. L(M) = { ww^R | w ∈ {a, b}*}.

Un AFND transita en función de: Un estado y un prefijo de cadena. El estado actual y el primer símbolo de la cadena. El próximo estado.

Un AFDM: Tiene menos estados que cualquier AFND equivalente. No puede tener estados inaccesibles. Puede tener configuraciones de bloqueo.

En un AFD: Tiene que haber tantas computaciones completas como cadenas aceptadas. Puede haber más computaciones completas que cadenas aceptadas. Puede haber menos computaciones completas que cadenas aceptadas.

Los autómatas con pila no deterministas: No pueden alcanzar estados de bloqueo. Generan lenguajes de tipo 1. Representan lenguajes de tipo 2.

El teorema de Myhill-Nerode se suele utilizar para demostrar que un lenguaje: Es de tipo 2 y no es de tipo 3. Es de tipo 0. No es regular.

Una GCL es ambigua sii: ∀ w ∈ L (G) / w es producto de más de un árbol de derivación. ∀ w ∈ L (G) / w es producto de infinitos árboles de derivación. ∃ w ∈ L(G) / w es producto de más de un árbol de derivación.

Una gramática es propia si: No es recursiva izquierda y no tiene símbolos inútiles. No es recursiva y no tiene símbolos inútiles. No es recursiva ni ambigua y no tiene símbolos inútiles.

La longitud de la computación de un AFND. Es siempre mayor que 1. Es infinita. Puede ser 0.

Marca la afirmación falsa: Si un símbolo de una gramática es útil entonces es accesible. Si un símbolo de una gramática es accesible y terminable entonces es útil. Si un símbolo de una gramática es útil entonces es terminable.

El AFD M = (K, Σ, δ, s, F) con K = {q0, q1} y Σ = {0, 1}, con la función de transición especificada por: δ (q0, 0) = q1, δ(q0, 1) = q0, δ(q1, 0) = q1, δ(q1, 1) = q0, y con s = q0 F = q1 representa: Un lenguaje con infinitas cadenas cuyo último símbolo es 0. El conjunto vacío. Un lenguaje con infinitas cadenas que no contienen 0.

Marca la afirmación verdadera: L∈ L.3 L <--> cumple la CBR. L∈ L.3 L --> cumple la CBR. L∈ L.3 L <-- cumple la CBR.

En un AFND una configuración: No puede ser inicial y terminal a la vez. Siempre tiene una siguiente. A veces puede transitar directamente a ella misma.

En un AFD una computación completa. No puede ser de longitud menor que dos. Puede ser de longitud cero. Puede estar bloqueada.

En un AF: Si hay estados inaccesibles entonces es un AFND. Si un estado es inaccesible entonces puede ser terminal. Si un estado es inaccesible entonces no puede ser final.

En un AFD la relación “transitar”: Es reflexiva. Es simétrica. Es el cierre transitivo de la relación “transitar directamente”.

Si una gramática es ambigua entonces: No puede ser regular. No puede ser recursiva. No siempre existe una no ambigua equivalente.

Marca la opción verdadera: Si una gramática es recursiva por la izquierda y derecha a la vez entonces no es regular. Una gramática no puede ser recursiva por la izquierda y derecha a la vez. Si una gramática es recursiva por la izquierda y derecha a la vez entonces no es ambigua.

Marca la opción verdadera: El axioma de una gramática siempre es un símbolo útil. Una gramática puede no tener ningún símbolo terminable. Que un símbolo sea terminable y accesible no implica que sea útil.

En un APND una configuración: No puede ser inicial y terminal a la vez. Siempre tiene una siguiente. A veces puede transitar directamente a ella misma.

Toda GCL que está en FNC cumple que: Ninguna regla tiene en la parte derecha más de dos símbolos. Ninguna regla tiene en la parte derecha menos de dos símbolos. Todas las reglas tienen en la parte derecha exactamente dos símbolos.

L = {0n1n}. Es un lenguaje de tipo 1. Es un lenguaje regular. Cumple la CBR.

El teorema de Myhill-Nerode suele usarse para: Demostrar que un lenguaje no es regular. Demostrar que un lenguaje no es vacío. Demostrar que un lenguaje es regular.

Identifica la expresión falsa: || L(AFND) || = || L(AFD) ||. L(AFND) = L.3. || L(AFND) || es no numerable.

Cuando un AF alcanza una configuración terminal: Podría transitar, pero sólo si es no determinista. Acepta la cadena. Queda bloqueado.

( q0, baababaaa ) ⊢ ( q1, ababaaa ) ⊢ ( q3, babaaa ). Es una computación de un posible AFD. Es una computación de un posible AFND. Es una computación completa.

Si un AFD rechaza una cadena w: Lo hace en |w| + 1 pasos. Lo hace en |w| pasos o menos. Lo hace en exactamente |w| pasos.

En un AFD el lenguaje aceptado. Nunca incluye la cadena vacía. Puede incluir la cadena vacía. Si incluye la cadena vacía entonces el lenguaje es infinito.

La incompletitud de los sistemas formales fue demostrada: Por Kurt Gödel. Por Alan Turing y Emil Post. Por Stephen C. Kleene en 1935.

El teorema de incompletitud de K. Gödel se publicó. En 1963. Después de 1963. Antes de 1936.

Sea M la MT especificada por la tabla indicada abajo, marque la configuración terminal que se obtiene para la configuración inicial (0, ...* || * || * ... ). 0 * L 1 0 | L 1 1 * | 2 1 | L 1 2 * L 3 2 | R 2 3 * L 4 3 | * 3 4 * h 4 4 | * 4. (4, ... * ||| * ... ). (0, ... * ||| * ... ). (4, ... * |||| * ... ).

En una composición. Siempre hay más funciones internas que externas. El número de funciones internas y externas puede coincidir. Siempre hay más funciones externas que internas.

La tercera columna de una tabla de una MT representa. La función de parada. La función de transición. La función de instrucción.

Elija la opción correcta: Todo conjunto perteneciente al conjunto potencia de los naturales es un conjunto decidible. Un conjunto perteneciente al conjunto potencia de los naturales puede no ser enumerable ni decidible. Todo conjunto perteneciente al conjunto potencia de los naturales es un conjunto enumerable.

Una Máquina de Turing de un estado sobre una cinta no vacía. Puede parar sobre el cuadrado escrutado inicial. Nunca se para. Para con cualquier contenido de la cinta.

En una tabla de una MT. Si en la tercera columna no hay elementos repetidos entonces tiene menos de tres estados. En la tercera columna siempre hay elementos repetidos. Si en la tercera columna hay elementos repetidos entonces tiene más de dos estados.

Si un conjunto es vacío su función característica. Siempre vale uno. No existe. Siempre vale cero.

Un predicado es recursivamente decidible. Sí y sólo si su función característica asociada es parcial. Si es el predicado asociado de alguna función recursiva total. Si es enumerable.

Sea Q = (1, 2, s) un programa WHILE cuyo código se describe a continuación: s: X2 := X1 – 1 ; while X1 ≠ 0 do X1 := X1 – 1 ; X1 := X1 – 1 ; X1 := X1 – 1 ; X2 := X2 + 1 ; X2 := X2 + 1 ; X2 := X2 + 1 od ; X1 := X2. CALQ(5, 4) = (5, 4, 4). CALQ(5, 4) = (5, 4, 5). CALQ(5, 4) = (5, 3, 4).

La función complejidad Temporal (T). No puede calcularse cuando no es posible alcanzar una configuración terminal. Es una función total. Para una entrada dada nos da el valor de la variable X1 al final del proceso de cómputo, siempre que se alcance una configuración terminal.

La tabla de una MT con tres estados y dos símbolos tiene: Nueve filas. Cinco columnas. Seis filas, o menos.

Dado un código While S, se cumple que: La función salto(s, n) es una función parcial. La función salto(s, n) puede devolver un valor menor que n. La función salto(s, n) siempre devuelve un valor mayor que n.

Sea Q = (1, 2, s) con s: X2:=X1; While X2≠ 0 do X1 := X1 + 1 ; X2 := X2 - 1 ; od. TQ(n)=2n+2 ∀ n ∈ N. TQ(n)=3n+3 ∀ n ∈ N. TQ(n)=4n+2 ∀ n ∈ N.

σ(θ) es: Una función constante. Una recursión primitiva de funciones iniciales. Una función recursiva parcial.

Indicar el valor de la función f(n, m) = suma (resta (π21, π 22), resta (π 22, π 21)) (n, m) para n=3 m=2, donde suma es la función “suma” entre dos naturales y resta es la función “resta natural” entre dos naturales es: f(3, 2) = 6. f(3, 2) = 1. f(3, 2) = 5.

Que un conjunto sea Turing-decidible significa que. Alan Turing decidió que dicho conjunto merecía ser analizado. Existe una función Turing-calculable que enumera el conjunto en un tiempo finitoc. El complementario de dicho conjunto es también decidible.

El cierre de INI respecto a la composición y la minimización no acotada es. TREC. F(WHILE). El conjunto de las funciones representables.

Una MT puede realizar. Cinco o más instrucciones elementales. Cuatro instrucciones elementales. Infinitas instrucciones elementales.

Los orígenes de la palabra “algoritmo”. Se sitúan en 1936. Son anteriores a 1936. Son posteriores a 1936.

Sea Q = (1, 2, s) un programa WHILE cuyo código se describe a continuación: s: X2 := X1 + 1 ; while X1 ≠ 0 do X1 := X1 – 1 ; X1 := X1 – 1 ; X2 := X2 + 1 ; X2 := X2 + 1 ; od ; X1 := X2. CALQ(2,4) = (4, 1, 3). CALQ(2,4) = (5, 0, 3). CALQ(2,4) = (5, 1, 3).

Sea M la MT especificada por la tabla 0 * | 1 0 | r 0 1 * r 2 1 | r 2 2 * h 2 2 | h 2. Un método de operación de M es ( ...* w *... ) * ( ...* w * ... ). Un método de operación de M es ( ...* ｜ *... ) * ( ...* *... ). Un método de operación de M es ( ...* w *... ) ⊢* ( ...* w ｜*... ).

Una MT puede ejecutar el siguiente método de operación: (…*w*... ⇒ …*ww*...). Sólo si ejecuta la instrucción "halt". Conteste esta respuesta si quiere que la pregunta sea errónea, en otro caso, seleccione la otra.

Una tabla de una MT. Siempre tiene más estados que símbolos en su alfabeto. No puede tener menos de dos líneas. Siempre tiene un número par de líneas.

Un predicado de PRED (T-MT) es un predicado. Decidible. Cuyo valor de verdad no está definido para algunos argumentos. Ninguna de las otras opciones es cierta.

Σ (n) es. La función castor afanoso. Una función computable. Una función no representable.

H1 es un problema. Resoluble. Totalmente no resoluble. Parcialmente resoluble.

¿Qué afirmación es correcta?. Σ(n) > Σ(n+1). Σ(n) < Σ(n+1). Σ(n) = Σ(n+1).

El conjunto de los lenguajes de contexto libre: No es cerrado para la potencia. No es cerrado para el complemento. Es cerrado para la intersección.

Sea el programa WHILE Q = (1, 1, X1:=X1+1). FQ = σ (con σ ∈ INI). CALQ(3, 2) = (4, 5). TQ(3) = 4.

Sean Q y R dos programas WHILE distintos de 1 argumento, entonces: CODI (Q) ≠ CODI (R). FQ (x) ≠ FR (y), ∀ x, y ∈ N. (FQ (x), FR (y)) ∈ N2, ∀ x, y ∈ N.

Una configuración de un programa WHILE siempre tiene al menos: Una componente. Dos componentes. Tres componentes.

El Teorema de Equivalencia demuestra que: L (AF) = L.3. REC = F(WHILE). TREC = T-MT.

Marca la afirmación falsa: La regla ABA -> BABA es sensible al contexto. La regla AA -> BB es de tipo uno. La regla ABA -> BBA es sensible al contexto.

Marca la opción verdadera: F (n, p, s) = F (n+i, p, s). F (n, p, s) = F (n+i, p+i, s). F (n, p, s) = F (n, p+i, s).

Marca la opción verdadera: f = μ[g] -> f ∈ F(WHILE). f = g(h) ^ g, h ∈ TREC -> f ∈ T-WHILE. f = g(h) ^ f ∉ REC -> g ∉ F(WHILE).

Si σ12(3, 4) = 32 entonces: Codi (X3 := X4-1) = 162. Codi (X4 := X5-1) = 163. Codi (X4 := X5-1) = 162.

Marca la opción verdadera: μ [ U [REC^1 ] ] ∈ TREC. μ [ U [REC^100 ] ] ∈ REC^100. μ [ U [REC^100 ] ] ∈ REC^101.

Marca la opción verdadera: DEC (MT) = REC. F(WHILE) ⊆ REC. PRED(MT) ⊆ F(WHILE).

El programa Reducir tiene: Una entrada. Dos entradas. Tres entradas.

La función degod es: Sobreyectiva pero no inyectiva. Biyectiva pero no recursiva. Biyectiva y recursiva.

Si un problema es no resoluble entonces: El predicado del que es asociado puede ser enumerable. El predicado del que es asociado no puede ser enumerable. No puede ser parcialmente resoluble.

Marca la opción verdadera: F = < g|h > -> f ∈ REC. F = μ[g] ^ g ∈ T-WHILE -> f ∈ T-WHILE. F = μ[g] ^ f ∉ F(WHILE) -> g ∉ F(WHILE).

La función god es. Sobreyectiva pero no inyectiva. Biyectiva pero no recursiva. Biyectiva y recursiva.

Marca la opción verdadera: WHILE ⊂ WHILE_A. WHILE = WHILE_A. F(WHILE) ⊂ F(WHILE_A).

Si la definición de la función castor afanoso le añadimos que Σ(0)=0 entonces. Σ ∈ TREC. Σ es una función total pero no recursiva. La función Σ no es ni total ni recursiva.

El cardinal de las funciones computables es: Menor que el de las funciones no calculables. Mayor que el de las funciones representables. Menor que el de las funciones totales.

Elija la opción correcta: F (n, p, s) = F (n+i, p+i, s), donde p = max {n, k} con k = max { m ∈ Σ+d | Xm < S }. F (n, p, s) = F (n, p+i, s), donde p = max {n, k} con k = max { m ∈ Σ+d | Xm < S }. (n, p, s) = F (n+i, p, s), donde p = max {n, k} con k = max { m ∈ Σ+d | Xm < S }.

Codi (X1 := 0; X1 := X1-1). 34. 32. 64.

Toda indexación de funciones es. Biyectiva. Sobreyectiva. Invertible.

El predicado H1 es parcialmente resoluble. Porque es el predicado asociado a la función computable f = σ (U [ REC1]). Porque es el predicado asociado a la función Σ. Porque no es resoluble.

Elija la opción correcta: U [REC n] ∈ REC n+1. U [REC 1] es una función total. U [REC n] ∈ REC n.

Marque la opción falsa: Todo predicado enumerable es decidible. Toda función total es computable. El cardinal de T-REC es igual al cardinal de REC.