Si A es un conjunto finito y R es una relación sobre A entonces:	R puede ser antisimétrica aunque sea reflexiva
Dado un alfabeto cualquiera Σ, el conjunto de las cadenas con longitud n ∈ N que se puede formar con sus símbolos tiene cardinalidad:	finita
La cardinalidad de {n∈R:n>100} es	infinita no numerable
¿Cuál de estas proposiciones sobre la jerarquía de Chomsky es cierta?	L.0≠L.REP
El cardinal del conjunto potencia de los reales	no es alef cero ni es alef uno
Si f es una función monaria sobre A, con Dom(f) = Rg(f) = A, entonces:	f puede ser sobreyectiva sin ser inyectiva
El lenguaje representado por (00+1)* + (01)* y es de tipo	3 y no es finito
P({1,2}) =	{θ,{1},{2},{1,2}}
Sea el conjunto A ⊆ N, A = {n ∈ N \| n <= 10}, y sea A- el cierre estricto de A con la operación "resta natural" ¿A qué es igual A-?	A- = A
La suma de dos elementos de N0(+:N0xN0 →N0) es una función	sobreyectiva
En la función "suma de dos naturales", el dominio es el conjunto	NxN
la regla AA →aA	es de tipo 1 y no es de tipo 2
Siendo {(1,1),(2,2)} una relación binaria sobre {0,1,2}, ¿Cuál de estas relaciones es su cierre simétrico?	{(1,1),(2,2)}
¿Que expresion de las siguientes NO se corresponde con un lenguaje? ε, θ, Σ+	ε
Si un conjunto A no tiene subconjuntos propios, entonces:	\|\|A\|\| < 2
Dados los conjuntos A = {a,b,c,d}, Π1 = {a,c} y Π2 ) {b,d}	Π1 y Π2 definen una partición sobre A
θx{a,b}x{c,d} = ?	{a,b}x{c,d}xθ
Dado un alfabeto cualquiera Σ, el conjunto de las cadenas con longitud n ∈ N que se puede formar con sus símbolos tiene cardinalidad	finita
Utilizando la biyeccion de la demostracion de que Σ* es finito numerable, si Σ={a,b,c}, con esa ordenacion, y w = aaaab, entonces	f(w) = 122 ((3^4) * 1) + ((3^3) * 1) + ((3^2) * 1) + ((3^1) * 1) + ((3^0) * 2) = 81 + 27 + 9 + 3 + 2 = 122
¿Es cierta la proposición L.3⊃L.2⊃L.1⊃L.0 sobre la jerarquía de Chomsky?	NO
¿Es cierto que L.1 = L.2?	NO
¿Es cierto que L.0 != L.REP?	SI
Dada la expresion regular ((a+b)c), ¿Cual de las siguientes cadenas NO pertenece al lenguaje definido por dicha expresión? c, cb, bacc	cb
¿11111001 ∈ 10(10+01)* ?	Si
¿11111001 ∈ 1(10)1*?	No
Si dos conjuntos A y B son equipotenciales, ¿A y B tienen la misma cardinalidad?	Sí
Si dos conjuntos A y B son equipotenciales, ¿Existe una función f:A -> B biyectiva?	Sí
Si dos conjuntos A y B son equipotenciales, ¿A es un subconjunto propio de B o B es subconjunto propio de A?	Falso
Si G = (N,T,P,S) entonces	S⇒w, entonces w ∈ L(G), ∀w ∈ T
Dado una gramática cualquiera G, NO siempre podremos saber si el lenguaje que representa es vacío cuando G sea de tipo	Tipo 1
(0+10*)=	{0,1,10,100,...}
L(({A,B},{a,b},{A→Ab,A→aB,B→b},A))=	abb*
Dado el conjunto A = {a,b,c}, ¿Con que lenguaje se corresponde el cierre estricto de A con respecto a la operacion de concatenacion?	L((a+b+c)(a+b+c)*)
Si α es una expresión regular, entonces: αα-α = ?	αα-α = θ
Sea G = (N,T,P,S) con P = {S→ε}. Entonces ¿de qué tipo es G?	G es de tipo 0 pero no de tipo 1
Si una gramática G tiene una regla epsilon, entonces:	L(G) es del tipo 0 , y puede ser del tipo 3
¿(10)1* = (1+0)*?	Yes
¿01 = (01)*?	No
¿(0+1)1 = (0* + 1*)1?	Nope
Sea L1 y L2 lenguajes sobre Σ, si defino la operación *prefijos de L1 sobre L2", notado L1[L2 = {w∈L1 \| w es prefijo de alguna palabra de L2}, entonces	La operación no tiene elemento neutro
Identifica la expresión regular que representa el lenguaje (0+1)-110	110*
Utilizando la biyeccion de la demostracion de que Σ* es infinito numerable, si Σ1 ⊆ Σ2, y en los simbolos comunes coinciden la ordenación, entonces el numero de cadenas de Σ1* y Σ2* que tienen el mismo numero asignado es	\|\|Σ1\|\|+1
Si un conjunto A no tiene subconjuntos propios, entonces:	\|\| A \|\| < 2
¿Para toda relación R se cumple que R u I = R?	No
¿Para toda relación R se cumple que I^-1 != I?	No
¿Para toda relación R se cumple que R ∩ R^-1 = R^1- ∩ R?	SI
La regla baABAcA → baABaAcA	Es de tipo 1 y no es de tipo 2
Sean las gramaticas G1 = ({A},{a},{A→Aa},A) y G2 = ({A},{a},{A→aA},A). ¿G1 y G2 son equivalentes?	Si
Sean las gramaticas G1 = ({A},{a},{A→Aa},A) y G2 = ({A},{a},{A→aA},A) ¿L(G1) = L(G2) = {epsilon}?	No
Sean las gramaticas G1 = ({A},{a},{A→Aa},A) y G2 = ({A},{a},{A→aA},A) ¿Son ambas G1 y G2 lineales?	Si
Sea A un conjunto y R una relación tal que \|\| R \|\| = \|\| A x A \|\|:	R es simétrica, pero no antisimétrica
Sea A un conjunto y R una relación de equivalencia sobre A, y sea a ∈ A. Si [a] = A, entonces ¿cuántas clases de equivalencia habrá?	Si A = {a,b,c}, entonces si [a] = A, [a] = [b] = [c], por lo que son todas la misma clase de equivalencia (hay una solo).
Dada una gramática lineal G, entonces	G puede no ser ni lineal izquierda ni lineal derecha.
Si dos gramáticas G1 y G2 son equivalentes, entonces sus alfabetos terminales	pueden ser disjuntos. Dos gramáticas son equivalentes si generan el mismo lenguaje. Sean G1 tal que su alfabeto terminal es {a,b}, y G2 tal que su alfabeto terminal es {b,c}. Si ambas tienen P = ∅, ambas generan el lenguaje ∅, y tienen el alfabeto terminal disjunto (L(G1) ∩ L(G2) = ∅).
Sean cualesquieras alfabetos ∑₁ y ∑₂, el mínimo número de cadenas que tienen ∑₁* y ∑₂* en común su ordenación (usando la biyección de que ∑* es infinito numerable) es:	1. El cierre de Kleene de cualquier alfabeto contiene al menos el epsilon, luego, para 2 alfabetos cualesquiera, aunque sean totalmente disjuntos, siempre van a tener en la posición 0 a epsilon.
Sea G = (N,T,P,S) con P = ∅. Entonces:	G no genera nada, es decir, el lenguaje ∅, que por ser finito es regular (de tipo 3).
Sea el monoide (N,+) y sea B ⊆ N . Si B = B+ ∧ \|B\|\|>1 , entonces: \|\|B\|\| = ?	Alef cero
El cardinal del conjunto potencia de un conjunto:	Nunca es cero
Para toda relación R , su cierre reflexivo es:	R u I
Sean A={1,2} y B={3,4}. R={(1,4),(2,3)}	es una función biyectiva de A a B
Si (∀ x,y ∈Σ∗ \|x\| < \|y\| ⇒ x es prefijo de y ) entonces \|\|Σ\|\| = 1 ¿Verdadero o Falso?	Verdadero
Si x e y son cadenas sobre un alfabeto, entonces xy = yx ⇒ x = y ¿Verdadero o Falso?	Falso
Si una cadena x es sufijo y prefijo de otra cadena y entonces x = y ¿Verdadero o Falso?	Falso
La gramática G = ( {S}, {b}, { SS → bS }, S ) es de tipo	de tipo 1 y no es de tipo 2
\|x\|a = \|y\|a implica que	x = y, en el caso de que \|Σ\|=1
Un conjunto no numerable no tiene ningún subconjunto infinito numerable. ¿Verdadero o falso?	Falso
Todo conjunto numerable es equipotencial con N. ¿Verdadero o falso?	Falso
No todo subconjunto infinito de un conjunto no numerable es no numerable. ¿Verdadero o falso?	Verdadero
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 es el lenguaje generado por G?	(1100)* 0 0*
Una gramática es	una forma de representar lenguajes
¿Una gramática es un subconjunto de L.REP?	No
¿Una gramática es un algoritmo conclusivo para reconocer lenguajes?	No
(wx)2 = w2 x2, ∀ x,w ∈Σ∗ ¿Verdadero o falso?	Falso
(wx)R = xR wR, ∀ x,w ∈Σ∗ ¿Verdadero o falso?	Verdadero
x≠xR y y≠R ⇒ xy≠yx, ∀x,y∈Σ∗ ¿Verdadero o falso?	Falso
Una gramática generativa es	una forma de representar lenguajes
∥N∥=2ℵ0 ¿Verdadero o falso?	Falso
∥Q∥=2ℵ0 ¿Verdadero o falso?	Falso
∥R∥−∥N∥=2ℵ0 ¿Verdadero o falso?	Verdadero
Si G = (N,T,P,S) es lineal izquierda y lineal derecha a la vez, entonces	\|\|L(G)\|\| ≤ \|\|P\|\|
El conjunto de todos los lenguajes sobre un alfabeto es	infinito no numerable
El cierre amplio de un conjunto para una operación	incluye su cierre estricto
Si R es una relación de equivalencia y D su conjunto diagonal entonces:	\|\| D \|\| = 0
∀L ⊆ Σ∗, L∗ ∩ (L∗)R ≠ ∅ ¿Verdadero o falso?	Verdadero
∀L ⊆ Σ∗, L · LR = ( LR · L )R ¿Verdadero o falso?	Falso
∀ L1 , L2⊆ Σ∗, LR1 · LR2 = ( L1 · L2 )R ¿Verdadero o falso?	Falso
∅{ε} = {ε}∅ = {ε} ¿Verdadero o falso?	Falso
∅* = {ε}* ¿Verdadero o falso?	Verdadero
ε ∈ L ⇔ L+ = L* ¿Verdadero o falso?	Verdadero
Una subcadena de la cadena x sobre Σ es	ε^2
Las expresiones regulares pueden representar	pueden representar cualquier lenguaje de tipo 3
La regla ABA→BABA es sensible al contexto ¿Verdadero o falso?	Verdadero
La regla AB→BA es sensible al contexto ¿Verdadero o falso?	Falso
La regla a → aB es de tipo 1 ¿Verdadero o falso?	Falso
Si f es una función biyectiva, entonces	\|\| Dom(f ) \|\| = \|\| Rg(f ) \|\|
Todo lenguaje regular tiene al menos una expresión regular que lo representa ¿Verdadero o falso?	Verdadero
Todo lenguaje representable puede ser representado por una expresión regular ¿Verdadero o falso?	Falso
Existen gramáticas regulares que generan lenguajes que no son representables mediante expresiones regulares ¿Verdadero o falso?	Falso
¿\|Σ*\| > \|Σ\|?	No
¿\|Σ*\| > \|Σ+\|?	Si
\|ε\| = ?	\|ε\| = 0
Si A ={1,2,3} entonces	2A⊃ {A}
Si G = (N,T,P,S) es regular izquierda y regular derecha a la vez, entonces	\|\|L(G)\|\| ≤ \|\|T\|\|
El cierre simétrico de una relación R está definido como:	R∪R−1
Dados A ={1,2,3}, B= {4} y R={(1,4)}, se cumple que R es:	R es un subconjunto de A X B
Sean x e y cadenas sobre un alfabeto Σ. Se cumple que xy=yx si:	x = y
El conjunto de todos los posibles lenguajes representables sobre un alfabeto es:	Infinito numerable

Descubre

Crear Tarjetas

Acerca de Nosotros

Explore Tarjetas

Comparta este Set de Tarjetas de Aprendizaje

Tarjetas de Aprendizaje relacionadas

Talf Bloque 1

Cómo estudiar sus tarjetas

Rango de Cartas a estudiar

107 Cartas en este set