Test
Teoria de Automatas (Curso Completo)
Preguntas del test (49)
1Un AFD M...
- Adecide si una cadena pertenece o no a
L(M) - Bcontiene infinitos estados
- Cpuede representar cualquier lenguaje de
tipo 2
- Adecide si una cadena pertenece o no a
2Respecto a la operación de unión de
lenguajes:- Alos lenguajes sensibles al contexto no
son cerrados - Bsólo son cerrados los lenguajes regulares
y de contexto libre - Clos cinco tipos de lenguajes son cerrados
- Alos lenguajes sensibles al contexto no
3Si A={ 1,2,3} y B= {{1},{2,3}} entonces:
- AB es una partición de A
- BB es el conjunto potencia de A
- CB es un subconjunto de A
4Si una GCL es recursiva por la izquierda, entonces
- Agenera un lenguaje infinito
- Bexiste una gramática regular equivalente
- Cexiste una GCL equivalente que no es
recursiva por la izquierda
5Las expresiones regulares
- Apueden representar cualquier lenguaje
representable - Bno pueden representar lenguajes que
incluyan la cadena vacía - Cpueden representar cualquier lenguaje
de tipo 3
- Apueden representar cualquier lenguaje
6La función Castor Afanoso es
- Auna aplicación biyectiva entre naturales
- Bparcialmente resoluble
- Ccreciente ( m > n
7Un predicado es decidible
- Asi es enumerable
- Bsí y sólo si su función característica
asociada es parcial - Csi se puede encontrar su valor de verdad
cualesquiera que sean los argumentos
8F(WHILE) es un conjunto con cardinal
- Aigual al número de languajes no
representables - Binfinito no numerable
- Cigual que REC-TREC
- Aigual al número de languajes no
9Dado un lenguaje L:
- AL { ε } = L
- BL{ ε } = L∅
- CL{ ε } = ∅L
10Si M es un AFDM entonces
- Atodos los AFD equivalentes tienen menos
estados finales que M - Bexiste un AFD equivalente con menos
estados que M - Ctodos los AFD equivalentes tienen mayor
o igual número de estados que M
- Atodos los AFD equivalentes tienen menos
11Si un programa WHILE de tamaño 6 transita
directamente de (5, 1, 1) a (2, 1,1), entonces
su código- Ano contiene asignaciones a cero
- Bcontiene bucles
- Ccontiene seis asignaciones
12De acuerdo con la clasificación de los
lenguajes, se cumple que:- Alenguajes de tipo 3 ⊂ lenguajes de tipo 0
- Blenguajes con estructura de frase ⊂
lenguajes de tipo 2 - Clenguajes lineales ⊂ lenguajes regulares
13¿En cuál de los siguientes casos la gramática
será del tipo "independiente del contexto"?- ASi todas sus reglas son de tipo 1
- BSi al menos una de sus reglas es sensible
al contexto - CSi todas sus reglas son regulares
terminales
14Una gramática es
- Aun algoritmo conclusivo para reconocer
lenguajes - Buna forma de representar lenguajes
- Cun subconjunto de L.REP
- Aun algoritmo conclusivo para reconocer
15El cardinal de las funciones computables es:
- Amenor que el de las funciones no
calculables - Bmayor que el de las funciones
representables - Cmenor que el de las funciones totales
- Amenor que el de las funciones no
16¿Cuál de las siguientes expresiones identifica
un lenguaje sobre un alfabeto ?- A∥Σ∥
- B{ Σ+}
- C∅
17Del Teorema de Equivalencia podemos
concluir que:- Aexiste un programa universal
- BREC = F(T-WHILE)
- CREC ⊆ F(WHILE)
18El problema de la parada para programas con
una entrada (dado por el predicado H 1 )- Aes parcialmente resoluble
- B∈ TREC
- Ces no enumerable
19Un APND, con conjunto de estados finales F,
acepta una cadena w si y sólo si- A∃ q ∈ F / ( s, ε, w ) ⊢ ( q, ε, ε )
- B∃ q ∈ F / ( s, w, ε ) ⊢ ( q, ε, ε )
- C∃ q ∈ F / ( s, w, ε ) ⊢* ( q, ε, ε )
20Sean x e y cadenas sobre un alfabeto . Se
cumple que xy = yx si:- Ax =xR e y =yR
- B=yR e y ≠ϵ
- Cx = y
21Si A ={1,2,3} entonces
- A2^A ⊃ ∅
- B2^A ⊃ {A}
- C2^A ⊃ A^2
22Si A={1,2} y B={3,4}, entonces R={(1,4),
(2,3)}- Aes una función biyectiva de A a B
- Bes una función parcial de A a B
- Cno es una aplicación de A a B
23La función reemplazar del programa universal
(reem) es:- Auna función parcial de 3 argumentos
- Buna función total
- Cuna función inyectiva
24La gramática ( { A }, { a }, { A → Aa }, A )
- Arepresenta el lenguaje L={ }
- Bgenera la derivación A -> Aa -> Aaa
- Ces regular izquierda
25Si un lenguaje cumple la condición de
bombeo regular entonces- Apuede representarse con una expresión
regular - Bno hay un AFD que lo represente
- Cno podemos afirmar que es regular
- Apuede representarse con una expresión
26Una Máquina de Turing de un estado sobre
una cinta no vacía- Ano puede parar a más de dos posiciones
del cuadrado escrutado inicial - Bpuede parar sobre el cuadrado escrutado
inicial - Cpara con cualquier contenido de la cinta
- Ano puede parar a más de dos posiciones
27Toda GCL que está en FNC cumple que
- Aninguna regla tiene en la parte derecha
más de dos símbolos - Bninguna regla tiene en la parte derecha
menos de dos símbolos - Ctodas las reglas tienen en la parte
derecha exactamente dos símbolos
- Aninguna regla tiene en la parte derecha
28El 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:- Aun lenguaje con infinitas cadenas cuyo último
símbolo es 0 - Bun lenguaje con infinitas cadenas que no
contienen 0 - Cel conjunto vacío
- Aun lenguaje con infinitas cadenas cuyo último
29La gramática G = ( {S}, {b}, { SS → bS }, S
) es- Ade tipo 1 y no es de tipo 2
- Bde tipo 0 y no es de tipo 1
- Cde tipo 2 y no es de tipo 3
30Si A={1,2,3} y R={(1,1),(2,2)} entonces
- AR es una relación de equivalencia sobre A
- BR es una relación simétrica sobre A
- CR es una relación reflexiva sobre A
31Una función de indexación para un conjunto
de funciones tiene que ser:- Asobreyectiva
- Binyectiva
- Cbiyectiva
32Elija la opción correcta
- A∥N∥ = 2^ℵ0
- B∥R∥ − ∥N∥ = 2^ℵ0
- C∥Q∥ = 2^ℵ0
33L(AFD) =
- AL(APND)
- BL.2
- CL(AFND)
34"Principia Mathematica" fue escrito por
- AAlfred N. Whitehead y Bertrand Russell
- BStephen C. Kleene y Alonzo Church
- CAlan M. Turing
35La gramática ( { A }, { a }, { A → Aa, A →
aA }, A )- Agenera la derivación A -> Aa -> aAa
- Bno es regular
- Crepresenta el lenguaje { ε }
36Una GCL es ambigua sii
- A∃ w ∈ L(G) / w es producto de más de un
árbol de derivación - B∀ w ∈ L(G) / w es producto de más de un
árbol de derivación - C∀ w ∈ L(G) / w es producto de infinitos
árboles de derivación
- A∃ w ∈ L(G) / w es producto de más de un
37Sea Σ = {a,b,c}. Dado L = {w ∈ Σ* | aa no
es una subcadena de w }, una ER del mismo
es:- AL = (b+c)* (a+ε) ( (b+c) (a+ε) )*
(b+c)* - BL=(b+c)* a ( (b+c) a )* (b+c)*
- CL=(b+c)* (a+ε) (b+c) (a+ε)
- AL = (b+c)* (a+ε) ( (b+c) (a+ε) )*
38La función complejidad Temporal (T)
- Ano puede calcularse cuando no es posible
alcanzar una configuración terminal - Bpara 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 - Ces una función total
- Ano puede calcularse cuando no es posible
39Si M = ( {s,f}, {a,b}, {a,b}, {(( s, aa, ),
(s, b)), (( s, , ), (f, )), (( f, a, b), (f, ))},
s, {f} ) entonces- AL(M) = {wwwR ∣w ∈ {a,b} ∗ }
- BL(M) = {w ∈ {a,b} ∗ ∣w =a 3n con n ∈ ℕ}
- CL(M) = {wwR ∣w ∈ {a,b} ∗ }
40σ(θ) es:
- Auna recursión primitiva de funciones
iniciales - Buna función recursiva parcial
- Cuna función constante
- Auna recursión primitiva de funciones
41En el modelo de funciones recursivas, el
símbolo Pi ( ) representa:- Aun conjunto finito de funciones
- Bun subconjunto de TREC
- Cuna función inicial
42Elija la opción correcta:
- AN^2 y N no son equipotenciales
- BN* y N son equipotenciales
- Cexisten tantos vectores de tres naturales
como números naturales
43Dados A ={1,2,3}, B= {4} y R={(1,4)}, se
cumple que:- AR es un subconjunto de A x B
- BR es una relación binaria sobre A
- CR es una relación de equivalencia sobre A
44El cierre amplio de un conjunto para una
operación- Ano incluye el conjunto vacío
- Bno incluye el elemento neutro
- Cincluye su cierre estricto
45Dada una gramática G=(N,T,P,S), se cumple
que:- AN intersección T = Ø
- BN intersección T = S
- CN intersección T = V
46Dada una gramática, el conjunto de reglas de
producción P cumple que:- AP = N interseccion T
- BP (N interseccion T)+ × (N interseccion T)*
- CP = (N interseccion T)*
47Dada una gramática de tipo 2, siempre
podemos responder si:- Ael lenguaje que representa es vacío
- Bes equivalente a otra gramática de tipo 2
- Cexiste una gramática regular equivalente
48El teorema de Myhill-Nerode suele usarse
para:- Ademostrar que un lenguaje no es vacío
- Bdemostrar que un lenguaje es regular
- Cdemostrar que un lenguaje no es regular
49Si en un lenguaje sobre todas sus
cadenas son indistinguibles, entonces- AL = sigma*
- BL = Ø
- CLos 2 anteriores
Información
- Descripción
- Examen de febrero de la asignatura Teoría de Autómatas y Lenguajes Formales.
- Idioma
- Español
- Visitas
- 488
- Etiquetas
- Valoración
- Aún sin valoraciones Valora este test