Teoria de Automatas (Curso Completo)

Question 1 of 49

Medal-premium 1

Un AFD M...

Select one of the following:

  • decide si una cadena pertenece o no a
    L(M)

  • contiene infinitos estados

  • puede representar cualquier lenguaje de
    tipo 2

Question 2 of 49

Medal-premium 1

Respecto a la operación de unión de
lenguajes:

Select one of the following:

  • 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

Question 3 of 49

Medal-premium 1

Si A={ 1,2,3} y B= {{1},{2,3}} entonces:

Select one of the following:

  • B es una partición de A

  • B es el conjunto potencia de A

  • B es un subconjunto de A

Question 4 of 49

Medal-premium 1

Si una GCL es recursiva por la izquierda, entonces

Select one of the following:

  • genera un lenguaje infinito

  • existe una gramática regular equivalente

  • existe una GCL equivalente que no es
    recursiva por la izquierda

Question 5 of 49

Medal-premium 1

Las expresiones regulares

Select one of the following:

  • pueden representar cualquier lenguaje
    representable

  • no pueden representar lenguajes que
    incluyan la cadena vacía

  • pueden representar cualquier lenguaje
    de tipo 3

Question 6 of 49

Medal-premium 1

La función Castor Afanoso es

Select one of the following:

  • una aplicación biyectiva entre naturales

  • parcialmente resoluble

  • creciente ( m > n

Question 7 of 49

Medal-premium 1

Un predicado es decidible

Select one of the following:

  • 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

Question 8 of 49

Medal-premium 1

F(WHILE) es un conjunto con cardinal

Select one of the following:

  • igual al número de languajes no
    representables

  • infinito no numerable

  • igual que REC-TREC

Question 9 of 49

Medal-premium 1

Dado un lenguaje L:

Select one of the following:

  • L { ε } = L

  • L{ ε } = L∅

  • L{ ε } = ∅L

Question 10 of 49

Medal-premium 1

Si M es un AFDM entonces

Select one of the following:

  • 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

Question 11 of 49

Medal-premium 1

Si un programa WHILE de tamaño 6 transita
directamente de (5, 1, 1) a (2, 1,1), entonces
su código

Select one of the following:

  • no contiene asignaciones a cero

  • contiene bucles

  • contiene seis asignaciones

Question 12 of 49

Medal-premium 1

De acuerdo con la clasificación de los
lenguajes, se cumple que:

Select one of the following:

  • lenguajes de tipo 3 ⊂ lenguajes de tipo 0

  • lenguajes con estructura de frase ⊂
    lenguajes de tipo 2

  • lenguajes lineales ⊂ lenguajes regulares

Question 13 of 49

Medal-premium 1

¿En cuál de los siguientes casos la gramática
será del tipo "independiente del contexto"?

Select one of the following:

  • 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

Question 14 of 49

Medal-premium 1

Una gramática es

Select one of the following:

  • un algoritmo conclusivo para reconocer
    lenguajes

  • una forma de representar lenguajes

  • un subconjunto de L.REP

Question 15 of 49

Medal-premium 1

El cardinal de las funciones computables es:

Select one of the following:

  • menor que el de las funciones no
    calculables

  • mayor que el de las funciones
    representables

  • menor que el de las funciones totales

Question 16 of 49

Medal-premium 1

¿Cuál de las siguientes expresiones identifica
un lenguaje sobre un alfabeto ?

Select one of the following:

  • ∥Σ∥

  • { Σ+}

Question 17 of 49

Medal-premium 1

Del Teorema de Equivalencia podemos
concluir que:

Select one of the following:

  • existe un programa universal

  • REC = F(T-WHILE)

  • REC ⊆ F(WHILE)

Question 18 of 49

Medal-premium 1

El problema de la parada para programas con
una entrada (dado por el predicado H 1 )

Select one of the following:

  • es parcialmente resoluble

  • ∈ TREC

  • es no enumerable

Question 19 of 49

Medal-premium 1

Un APND, con conjunto de estados finales F,
acepta una cadena w si y sólo si

Select one of the following:

  • ∃ q ∈ F / ( s, ε, w ) ⊢ ( q, ε, ε )

  • ∃ q ∈ F / ( s, w, ε ) ⊢ ( q, ε, ε )

  • ∃ q ∈ F / ( s, w, ε ) ⊢* ( q, ε, ε )

Question 20 of 49

Medal-premium 1

Sean x e y cadenas sobre un alfabeto . Se
cumple que xy = yx si:

Select one of the following:

  • x =xR e y =yR

  • =yR e y ≠ϵ

  • x = y

Question 21 of 49

Medal-premium 1

Si A ={1,2,3} entonces

Select one of the following:

  • 2^A ⊃ ∅

  • 2^A ⊃ {A}

  • 2^A ⊃ A^2

Question 22 of 49

Medal-premium 1

Si A={1,2} y B={3,4}, entonces R={(1,4),
(2,3)}

Select one of the following:

  • 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

Question 23 of 49

Medal-premium 1

La función reemplazar del programa universal
(reem) es:

Select one of the following:

  • una función parcial de 3 argumentos

  • una función total

  • una función inyectiva

Question 24 of 49

Medal-premium 1

La gramática ( { A }, { a }, { A → Aa }, A )

Select one of the following:

  • representa el lenguaje L={ }

  • genera la derivación A -> Aa -> Aaa

  • es regular izquierda

Question 25 of 49

Medal-premium 1

Si un lenguaje cumple la condición de
bombeo regular entonces

Select one of the following:

  • puede representarse con una expresión
    regular

  • no hay un AFD que lo represente

  • no podemos afirmar que es regular

Question 26 of 49

Medal-premium 1

Una Máquina de Turing de un estado sobre
una cinta no vacía

Select one of the following:

  • 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

Question 27 of 49

Medal-premium 1

Toda GCL que está en FNC cumple que

Select one of the following:

  • 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

Question 28 of 49

Medal-premium 1

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:

Select one of the following:

  • un lenguaje con infinitas cadenas cuyo último
    símbolo es 0

  • un lenguaje con infinitas cadenas que no
    contienen 0

  • el conjunto vacío

Question 29 of 49

Medal-premium 1

La gramática G = ( {S}, {b}, { SS → bS }, S
) es

Select one of the following:

  • 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

Question 30 of 49

Medal-premium 1

Si A={1,2,3} y R={(1,1),(2,2)} entonces

Select one of the following:

  • 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

Question 31 of 49

Medal-premium 1

Una función de indexación para un conjunto
de funciones tiene que ser:

Select one of the following:

  • sobreyectiva

  • inyectiva

  • biyectiva

Question 32 of 49

Medal-premium 1

Elija la opción correcta

Select one of the following:

  • ∥N∥ = 2^ℵ0

  • ∥R∥ − ∥N∥ = 2^ℵ0

  • ∥Q∥ = 2^ℵ0

Question 33 of 49

Medal-premium 1

L(AFD) =

Select one of the following:

  • L(APND)

  • L.2

  • L(AFND)

Question 34 of 49

Medal-premium 1

"Principia Mathematica" fue escrito por

Select one of the following:

  • Alfred N. Whitehead y Bertrand Russell

  • Stephen C. Kleene y Alonzo Church

  • Alan M. Turing

Question 35 of 49

Medal-premium 1

La gramática ( { A }, { a }, { A → Aa, A →
aA }, A )

Select one of the following:

  • genera la derivación A -> Aa -> aAa

  • no es regular

  • representa el lenguaje { ε }

Question 36 of 49

Medal-premium 1

Una GCL es ambigua sii

Select one of the following:

  • ∃ 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

Question 37 of 49

Medal-premium 1

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

Select one of the following:

  • 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+ε)

Question 38 of 49

Medal-premium 1

La función complejidad Temporal (T)

Select one of the following:

  • 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

Question 39 of 49

Medal-premium 1

Si M = ( {s,f}, {a,b}, {a,b}, {(( s, aa, ),
(s, b)), (( s, , ), (f, )), (( f, a, b), (f, ))},
s, {f} ) entonces

Select one of the following:

  • L(M) = {wwwR ∣w ∈ {a,b} ∗ }

  • L(M) = {w ∈ {a,b} ∗ ∣w =a 3n con n ∈ ℕ}

  • L(M) = {wwR ∣w ∈ {a,b} ∗ }

Question 40 of 49

Medal-premium 1

σ(θ) es:

Select one of the following:

  • una recursión primitiva de funciones
    iniciales

  • una función recursiva parcial

  • una función constante

Question 41 of 49

Medal-premium 1

En el modelo de funciones recursivas, el
símbolo Pi ( ) representa:

Select one of the following:

  • un conjunto finito de funciones

  • un subconjunto de TREC

  • una función inicial

Question 42 of 49

Medal-premium 1

Elija la opción correcta:

Select one of the following:

  • N^2 y N no son equipotenciales

  • N* y N son equipotenciales

  • existen tantos vectores de tres naturales
    como números naturales

Question 43 of 49

Medal-premium 1

Dados A ={1,2,3}, B= {4} y R={(1,4)}, se
cumple que:

Select one of the following:

  • 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

Question 44 of 49

Medal-premium 1

El cierre amplio de un conjunto para una
operación

Select one of the following:

  • no incluye el conjunto vacío

  • no incluye el elemento neutro

  • incluye su cierre estricto

Question 45 of 49

Medal-premium 1

Dada una gramática G=(N,T,P,S), se cumple
que:

Select one of the following:

  • N intersección T = Ø

  • N intersección T = S

  • N intersección T = V

Question 46 of 49

Medal-premium 1

Dada una gramática, el conjunto de reglas de
producción P cumple que:

Select one of the following:

  • P = N interseccion T

  • P (N interseccion T)+ × (N interseccion T)*

  • P = (N interseccion T)*

Question 47 of 49

Medal-premium 1

Dada una gramática de tipo 2, siempre
podemos responder si:

Select one of the following:

  • el lenguaje que representa es vacío

  • es equivalente a otra gramática de tipo 2

  • existe una gramática regular equivalente

Question 48 of 49

Medal-premium 1

El teorema de Myhill-Nerode suele usarse
para:

Select one of the following:

  • demostrar que un lenguaje no es vacío

  • demostrar que un lenguaje es regular

  • demostrar que un lenguaje no es regular

Question 49 of 49

Medal-premium 1

Si en un lenguaje sobre todas sus
cadenas son indistinguibles, entonces

Select one of the following:

  • L = sigma*

  • L = Ø

  • Los 2 anteriores

Icon_fullscreen

Teoria de Automatas (Curso Completo)

blorkszb
Quiz by , created almost 3 years ago

Examen de febrero de la asignatura Teoría de Autómatas y Lenguajes Formales.

Eye 241
Pin 1
Balloon-left 0
Tags No tags specified
blorkszb
Created by blorkszb almost 3 years ago
Close