446401
Descripción
Test por Daniel Alvarez Valero, actualizado hace más de 1 año
|
Creado por Daniel Alvarez Valero
hace más de 10 años
|
|
Pregunta 1
Pregunta
Un AFD M...
Respuesta
-
decide si una cadena pertenece o no a L(M)
-
contiene infinitos estados
-
puede representar cualquier lenguaje de tipo 2
Pregunta 2
Pregunta
Respecto a la operación de unión de
lenguajes:
Respuesta
-
los lenguajes sensibles al contexto no son cerrados
-
sólo son cerrados los lenguajes regulares y de contexto libre
-
los cinco tipos de lenguajes son cerrados
Pregunta 3
Pregunta
Si A={ 1,2,3} y B= {{1},{2,3}} entonces:
Respuesta
-
B es una partición de A
-
B es el conjunto potencia de A
-
B es un subconjunto de A
Pregunta 4
Pregunta
Si una GCL es recursiva por la izquierda, entonces
Respuesta
-
genera un lenguaje infinito
-
existe una gramática regular equivalente
-
existe una GCL equivalente que no es recursiva por la izquierda
Pregunta 5
Pregunta
Las expresiones regulares
Respuesta
-
pueden representar cualquier lenguaje representable
-
no pueden representar lenguajes que incluyan la cadena vacía
-
pueden representar cualquier lenguaje de tipo 3
Pregunta 6
Pregunta
La función Castor Afanoso es
Respuesta
-
una aplicación biyectiva entre naturales
-
parcialmente resoluble
-
creciente ( m > n
Pregunta 7
Pregunta
Un predicado es decidible
Respuesta
-
si es enumerable
-
sí y sólo si su función característica asociada es parcial
-
si se puede encontrar su valor de verdad cualesquiera que sean los argumentos
Pregunta 8
Pregunta
F(WHILE) es un conjunto con cardinal
Respuesta
-
igual al número de languajes no representables
-
infinito no numerable
-
igual que REC-TREC
Pregunta 9
Pregunta
Dado un lenguaje L:
Respuesta
-
L { ε } = L
-
L{ ε } = L∅
-
L{ ε } = ∅L
Pregunta 10
Pregunta
Si M es un AFDM entonces
Respuesta
-
todos los AFD equivalentes tienen menos estados finales que M
-
existe un AFD equivalente con menos estados que M
-
todos los AFD equivalentes tienen mayor o igual número de estados que M
Pregunta 11
Pregunta
Si un programa WHILE de tamaño 6 transita
directamente de (5, 1, 1) a (2, 1,1), entonces
su código
Respuesta
-
no contiene asignaciones a cero
-
contiene bucles
-
contiene seis asignaciones
Pregunta 12
Pregunta
De acuerdo con la clasificación de los
lenguajes, se cumple que:
Respuesta
-
lenguajes de tipo 3 ⊂ lenguajes de tipo 0
-
lenguajes con estructura de frase ⊂ lenguajes de tipo 2
-
lenguajes lineales ⊂ lenguajes regulares
Pregunta 13
Pregunta
¿En cuál de los siguientes casos la gramática
será del tipo "independiente del contexto"?
Respuesta
-
Si todas sus reglas son de tipo 1
-
Si al menos una de sus reglas es sensible al contexto
-
Si todas sus reglas son regulares terminales
Pregunta 14
Pregunta
Una gramática es
Respuesta
-
un algoritmo conclusivo para reconocer lenguajes
-
una forma de representar lenguajes
-
un subconjunto de L.REP
Pregunta 15
Pregunta
El cardinal de las funciones computables es:
Respuesta
-
menor que el de las funciones no calculables
-
mayor que el de las funciones representables
-
menor que el de las funciones totales
Pregunta 16
Pregunta
¿Cuál de las siguientes expresiones identifica
un lenguaje sobre un alfabeto ?
Respuesta
-
∥Σ∥
-
{ Σ+}
-
∅
Pregunta 17
Pregunta
Del Teorema de Equivalencia podemos
concluir que:
Respuesta
-
existe un programa universal
-
REC = F(T-WHILE)
-
REC ⊆ F(WHILE)
Pregunta 18
Pregunta
El problema de la parada para programas con
una entrada (dado por el predicado H 1 )
Respuesta
-
es parcialmente resoluble
-
∈ TREC
-
es no enumerable
Pregunta 19
Pregunta
Un APND, con conjunto de estados finales F,
acepta una cadena w si y sólo si
Respuesta
-
∃ q ∈ F / ( s, ε, w ) ⊢ ( q, ε, ε )
-
∃ q ∈ F / ( s, w, ε ) ⊢ ( q, ε, ε )
-
∃ q ∈ F / ( s, w, ε ) ⊢* ( q, ε, ε )
Pregunta 20
Pregunta
Sean x e y cadenas sobre un alfabeto . Se
cumple que xy = yx si:
Respuesta
-
x =xR e y =yR
-
=yR e y ≠ϵ
-
x = y
Pregunta 21
Pregunta
Si A ={1,2,3} entonces
Respuesta
-
2^A ⊃ ∅
-
2^A ⊃ {A}
-
2^A ⊃ A^2
Pregunta 22
Pregunta
Si A={1,2} y B={3,4}, entonces R={(1,4),
(2,3)}
Respuesta
-
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
Pregunta 23
Pregunta
La función reemplazar del programa universal
(reem) es:
Respuesta
-
una función parcial de 3 argumentos
-
una función total
-
una función inyectiva
Pregunta 24
Pregunta
La gramática ( { A }, { a }, { A → Aa }, A )
Respuesta
-
representa el lenguaje L={ }
-
genera la derivación A -> Aa -> Aaa
-
es regular izquierda
Pregunta 25
Pregunta
Si un lenguaje cumple la condición de
bombeo regular entonces
Respuesta
-
puede representarse con una expresión regular
-
no hay un AFD que lo represente
-
no podemos afirmar que es regular
Pregunta 26
Pregunta
Una Máquina de Turing de un estado sobre
una cinta no vacía
Respuesta
-
no puede parar a más de dos posiciones del cuadrado escrutado inicial
-
puede parar sobre el cuadrado escrutado inicial
-
para con cualquier contenido de la cinta
Pregunta 27
Pregunta
Toda GCL que está en FNC cumple que
Respuesta
-
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
Pregunta 28
Pregunta
El AFD M=(K, , ,s, F) con K={ , } y ={0,1}, con la
función de transición especificada por:
δ(q 0 , 0) = q 1 , δ(q 0 , 1) = q 0 , δ(q 1 , 0) = q 1 , δ(q 1 , 1) = q 0 ,
y con s=q0 F=q1 representa:
Respuesta
-
un lenguaje con infinitas cadenas cuyo último símbolo es 0
-
un lenguaje con infinitas cadenas que no contienen 0
-
el conjunto vacío
Pregunta 29
Pregunta
La gramática G = ( {S}, {b}, { SS → bS }, S
) es
Respuesta
-
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
Pregunta 30
Pregunta
Si A={1,2,3} y R={(1,1),(2,2)} entonces
Respuesta
-
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
Pregunta 31
Pregunta
Una función de indexación para un conjunto
de funciones tiene que ser:
Respuesta
-
sobreyectiva
-
inyectiva
-
biyectiva
Pregunta 32
Pregunta
Elija la opción correcta
Respuesta
-
∥N∥ = 2^ℵ0
-
∥R∥ − ∥N∥ = 2^ℵ0
-
∥Q∥ = 2^ℵ0
Pregunta 33
Pregunta
L(AFD) =
Respuesta
-
L(APND)
-
L.2
-
L(AFND)
Pregunta 34
Pregunta
"Principia Mathematica" fue escrito por
Respuesta
-
Alfred N. Whitehead y Bertrand Russell
-
Stephen C. Kleene y Alonzo Church
-
Alan M. Turing
Pregunta 35
Pregunta
La gramática ( { A }, { a }, { A → Aa, A →
aA }, A )
Respuesta
-
genera la derivación A -> Aa -> aAa
-
no es regular
-
representa el lenguaje { ε }
Pregunta 36
Pregunta
Una GCL es ambigua sii
Respuesta
-
∃ w ∈ L(G) / w es producto de más de un árbol de derivación
-
∀ 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
Pregunta 37
Pregunta
Sea Σ = {a,b,c}. Dado L = {w ∈ Σ* | aa no
es una subcadena de w }, una ER del mismo
es:
Respuesta
-
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+ε)
Pregunta 38
Pregunta
La función complejidad Temporal (T)
Respuesta
-
no puede calcularse cuando no es posible alcanzar una configuración terminal
-
para una entrada dada nos da el valor de la variable X1al final del proceso de cómputo, siempre que se alcance una configuración terminal
-
es una función total
Pregunta 39
Pregunta
Si M = ( {s,f}, {a,b}, {a,b}, {(( s, aa, ),
(s, b)), (( s, , ), (f, )), (( f, a, b), (f, ))},
s, {f} ) entonces
Respuesta
-
L(M) = {wwwR ∣w ∈ {a,b} ∗ }
-
L(M) = {w ∈ {a,b} ∗ ∣w =a 3n con n ∈ ℕ}
-
L(M) = {wwR ∣w ∈ {a,b} ∗ }
Pregunta 40
Pregunta
σ(θ) es:
Respuesta
-
una recursión primitiva de funciones iniciales
-
una función recursiva parcial
-
una función constante
Pregunta 41
Pregunta
En el modelo de funciones recursivas, el
símbolo Pi ( ) representa:
Respuesta
-
un conjunto finito de funciones
-
un subconjunto de TREC
-
una función inicial
Pregunta 42
Pregunta
Elija la opción correcta:
Respuesta
-
N^2 y N no son equipotenciales
-
N* y N son equipotenciales
-
existen tantos vectores de tres naturales como números naturales
Pregunta 43
Pregunta
Dados A ={1,2,3}, B= {4} y R={(1,4)}, se
cumple que:
Respuesta
-
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
Pregunta 44
Pregunta
El cierre amplio de un conjunto para una
operación
Respuesta
-
no incluye el conjunto vacío
-
no incluye el elemento neutro
-
incluye su cierre estricto
Pregunta 45
Pregunta
Dada una gramática G=(N,T,P,S), se cumple
que:
Respuesta
-
N intersección T = Ø
-
N intersección T = S
-
N intersección T = V
Pregunta 46
Pregunta
Dada una gramática, el conjunto de reglas de
producción P cumple que:
Respuesta
-
P = N interseccion T
-
P (N interseccion T)+ × (N interseccion T)*
-
P = (N interseccion T)*
Pregunta 47
Pregunta
Dada una gramática de tipo 2, siempre
podemos responder si:
Respuesta
-
el lenguaje que representa es vacío
-
es equivalente a otra gramática de tipo 2
-
existe una gramática regular equivalente
Pregunta 48
Pregunta
El teorema de Myhill-Nerode suele usarse
para:
Respuesta
-
demostrar que un lenguaje no es vacío
-
demostrar que un lenguaje es regular
-
demostrar que un lenguaje no es regular
Pregunta 49
Pregunta
Si en un lenguaje sobre todas sus
cadenas son indistinguibles, entonces
Respuesta
-
L = sigma*
-
L = Ø
-
Los 2 anteriores
¿Quieres crear tus propios Tests gratis con GoConqr? Más información.