Test talf bloque 1

Dado una gramática cualquiera G, NO siempre podremos saber si el lenguaje que representa es vacío cuando G sea de tipo. 1. 2. 3.

la regla AA →aA. es de tipo 2 y no es de tipo 3. es de tipo 1 y no es de tipo 2. es de tipo 3.

¿Cúal de estas proposiciones sobre relaciones es cierta? (Para toda relación R). I^-1 ≠ I. R ∪ I = R. R ∩ R^-1 = R^1- ∩ R.

El lenguaje representado por (00+1)* + (01)* y es de tipo. 2 y no es de tipo 3. 0 y no es de tipo 1. 3 y no es finito.

Si G = (N,T,P,S) entonces. ∃α ∈ ER | L(α) = L(G). S⇒*w, entonces w ∈ L(G), ∀w ∈ T*. L(G)⊆N*.

En la función "suma de dos naturales", el dominio es el conjunto. NxN. N. R.

θx{a,b}x{c,d}. {(c,d)}. {a,b}x{c,d}xθ. {(a,c),(a,d),(b,c)(b,d)}.

L(({A,B},{a,b},{A→Ab,A→aB,B→b},A))=. a*(a+b)*. ba*. abb*.

La regla baABAcA → baABaAcA. es de tipo 0 y no es de tipo 1. es de tipo 2 y no es de tipo 3. es de tipo 1 y no es de tipo 2.

La cardinalidad de {n∈R:n>100} es. finita. infinita numerable. infinita no numerable.

P({1,2}) =. {1}X{2}. {θ,{1},{2},{1,2}}. {{1},{2}}.

¿Cuál de estas condiciones es suficiente para que {A1,A2} sea partición del conjunto A?. A1∩A2 = θ. |A1| + |A2| = 0. ninguna de las otras condiciones es suficiente.

11111001 ∈. 1*0*(10+01)*. 1*(0110)*. 1*(10)*1*.

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),(1,2),(2,1),(2,2)}. {(0,0),(0,1),(1,0),(2,0),(0,2)}. {(1,1),(2,2)}.

Dado un alfabeto cualquiera Σ, el conjunto de las cadenas con longitud n ∈ N que se puede formar con sus símbolos tiene cardinalidad. N1. N0. finita.

Identifica la expresión regular que representa el lenguaje (0+1)*-110*. 110*. negado(110*). 110.

(0+10*)=. {1,010,0100,01000,...}. {0,1,10,100,...}. {ε,01,011,011,...}.

La suma de dos elementos de N0(+:N0xN0 →N0) es una función. sobreyectiva. biyectiva. inyectiva.

¿Cuál de estas proposiciones sobre la jerarquía de Chomsky es cierta?. L.0≠L.REP. L.1 = L.2. L.3⊃L.2⊃L.1⊃L.0.

¿Cuál de las siguientes igualdades de expresiones regulares son ciertas?. (1*0)*1* = (1+0)*. 0*1* = (01)*. (0+1)*1* = (0*+1*)1.

si f es una función monaria sobre A, con Dom(f) = Rg(f) = A, entonces: f puede ser inyectiva sin ser sobreyectiva. f puede ser sobreyectiva sin ser inyectiva. f es biyectiva.

Si α es una expresión regular, entonces: αα*-α* ={ε}. αα*-α* = θ. αα*-α* = α.

Dados los conjuntos A = {a,b,c,d}, Π1 = {a,c} y Π2 ) {b,d}. Π1 y Π2 definen una partición sobre A. Π1 y Π2 son clases de equivalencia. Π1 y Π2 definen una relación sobre A.

Sea G = (N,T,P,S) con P = {S→ε}. Entonces. G es de tipo 3. G es de tipo 1 pero no de tipo 2. G es de tipo 0 pero no de tipo 1.

El cardinal del conjunto potencia de los reales. No es N0 (alef cero) y si es N1(alef uno). No es N0 (alef cero) y no es N1(alef uno). No es N1 (alef uno) y si es N0(alef cero).

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- = Z. A- = A. A- = N.

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. {ε} es el elemento neutro de la operación. Σ* es el elemento neutro de la operación. la operación no tiene elemento neutro.

Si A es un conjunto finito y R es una relación sobre A entonces: si R no es simétrica es antisimétrica. R puede ser antisimétrica aunque sea reflexiva. si R es transitiva no puede ser antisimétrica.

Si una gramática G tiene una regla epsilon, entonces: L(G) es del tipo 0 , y puede ser del tipo 3. L(G) solo es del tipo 0 , y de ningun otro tipo. L(G) es del tipo 0, y puede ser del tipo 1 , pero nunca del tipo 2.

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||+1. ||Σ1||-1.

Dada la expresion regular ((a+b)*c*), ¿Cual de las siguientes cadenas NO pertenece al lenguaje definido por dicha expresión?. bacc. cb. c.

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)*). L((a+b+c)(a+b+c)*). L(a*+b*+c*).

Si dos conjuntos A y B son equipotenciales, ¿Cual de las siguientes afirmaciones es FALSA?. Existe una funcion, f: A →B biyectiva. A es un subcojunto propio de B o B es subconjunto propio de A. A y B tienen la misma cardinalidad.

Si un conjunto A no tiene subconjuntos propios, entonces: A = θ. ||A|| < 2. ||A|| = 1.

¿Que expresion de las siguientes NO se corresponde con un lenguaje?. θ. ε. Σ+.

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. f(w) = 121. f(w) = 123.

Sean las gramaticas G1 = ({A},{a},{A→Aa},A) y G2 = ({A},{a},{A→aA},A). Señala la afirmacion INCORRECTA. L(G1) = L(G2) = {ε}. G1 y G2 son equivalentes. G1 y G2 son ambas lineales.