Un AFD M...
decide si una cadena pertenece o no a L(M)
contiene infinitos estados
puede representar cualquier lenguaje de tipo 2
Respecto a la operación de unión de lenguajes:
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
Si A={ 1,2,3} y B= {{1},{2,3}} entonces:
B es una partición de A
B es el conjunto potencia de A
B es un subconjunto de A
Si una GCL es recursiva por la izquierda, entonces
genera un lenguaje infinito
existe una gramática regular equivalente
existe una GCL equivalente que no es recursiva por la izquierda
Las expresiones regulares
pueden representar cualquier lenguaje representable
no pueden representar lenguajes que incluyan la cadena vacía
pueden representar cualquier lenguaje de tipo 3
La función Castor Afanoso es
una aplicación biyectiva entre naturales
parcialmente resoluble
creciente ( m > n
Un predicado es decidible
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
F(WHILE) es un conjunto con cardinal
igual al número de languajes no representables
infinito no numerable
igual que REC-TREC
Dado un lenguaje L:
L { ε } = L
L{ ε } = L∅
L{ ε } = ∅L
Si M es un AFDM entonces
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
Si un programa WHILE de tamaño 6 transita directamente de (5, 1, 1) a (2, 1,1), entonces su código
no contiene asignaciones a cero
contiene bucles
contiene seis asignaciones
De acuerdo con la clasificación de los lenguajes, se cumple que:
lenguajes de tipo 3 ⊂ lenguajes de tipo 0
lenguajes con estructura de frase ⊂ lenguajes de tipo 2
lenguajes lineales ⊂ lenguajes regulares
¿En cuál de los siguientes casos la gramática será del tipo "independiente del contexto"?
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
Una gramática es
un algoritmo conclusivo para reconocer lenguajes
una forma de representar lenguajes
un subconjunto de L.REP
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
¿Cuál de las siguientes expresiones identifica un lenguaje sobre un alfabeto ?
∥Σ∥
{ Σ+}
∅
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 H 1 )
es parcialmente resoluble
∈ TREC
es no enumerable
Un APND, con conjunto de estados finales F, acepta una cadena w si y sólo si
∃ q ∈ F / ( s, ε, w ) ⊢ ( q, ε, ε )
∃ q ∈ F / ( s, w, ε ) ⊢ ( q, ε, ε )
∃ q ∈ F / ( s, w, ε ) ⊢* ( q, ε, ε )
Sean x e y cadenas sobre un alfabeto . Se cumple que xy = yx si:
x =xR e y =yR
=yR e y ≠ϵ
x = y
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 función reemplazar del programa universal (reem) es:
una función parcial de 3 argumentos
una función total
una función inyectiva
La gramática ( { A }, { a }, { A → Aa }, A )
representa el lenguaje L={ }
genera la derivación A -> Aa -> Aaa
es regular izquierda
Si un lenguaje cumple la condición de bombeo regular entonces
puede representarse con una expresión regular
no hay un AFD que lo represente
no podemos afirmar que es regular
Una Máquina de Turing de un estado sobre una cinta no vacía
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
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
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:
un lenguaje con infinitas cadenas cuyo último símbolo es 0
un lenguaje con infinitas cadenas que no contienen 0
el conjunto vacío
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
Una función de indexación para un conjunto de funciones tiene que ser:
sobreyectiva
inyectiva
biyectiva
Elija la opción correcta
∥N∥ = 2^ℵ0
∥R∥ − ∥N∥ = 2^ℵ0
∥Q∥ = 2^ℵ0
L(AFD) =
L(APND)
L.2
L(AFND)
"Principia Mathematica" fue escrito por
Alfred N. Whitehead y Bertrand Russell
Stephen C. Kleene y Alonzo Church
Alan M. Turing
La gramática ( { A }, { a }, { A → Aa, A → aA }, A )
genera la derivación A -> Aa -> aAa
no es regular
representa el lenguaje { ε }
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 más de un árbol de derivación
∀ w ∈ L(G) / w es producto de infinitos árboles de derivación
Sea Σ = {a,b,c}. Dado L = {w ∈ Σ* | aa no es una 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+ε)
La función complejidad Temporal (T)
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
Si M = ( {s,f}, {a,b}, {a,b}, {(( s, aa, ), (s, b)), (( s, , ), (f, )), (( f, a, b), (f, ))}, s, {f} ) entonces
L(M) = {wwwR ∣w ∈ {a,b} ∗ }
L(M) = {w ∈ {a,b} ∗ ∣w =a 3n con n ∈ ℕ}
L(M) = {wwR ∣w ∈ {a,b} ∗ }
σ(θ) es:
una recursión primitiva de funciones iniciales
una función recursiva parcial
una función constante
En el modelo de funciones recursivas, el símbolo Pi ( ) representa:
un conjunto finito de funciones
un subconjunto de TREC
una función inicial
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
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
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
Dada una gramática G=(N,T,P,S), se cumple que:
N intersección T = Ø
N intersección T = S
N intersección T = V
Dada una gramática, el conjunto de reglas de producción P cumple que:
P = N interseccion T
P (N interseccion T)+ × (N interseccion T)*
P = (N interseccion T)*
Dada una gramática de tipo 2, siempre podemos responder si:
el lenguaje que representa es vacío
es equivalente a otra gramática de tipo 2
El teorema de Myhill-Nerode suele usarse para:
demostrar que un lenguaje no es vacío
demostrar que un lenguaje es regular
demostrar que un lenguaje no es regular
Si en un lenguaje sobre todas sus cadenas son indistinguibles, entonces
L = sigma*
L = Ø
Los 2 anteriores
