TALF Bloque 1 2020/2021

Si f es una función monaria sobre A, con Dom(f) = Rg(f), 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}, Π₁ = {a,c}, Π₂ = {b,d}, entonces: Π₁ y Π₂ definen una partición sobre A. Π₁ y Π₂ son clases de equivalencia. Π₁ y Π₂ 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 ℵ₀ (alef cero) y si es ℵ₁ (alef uno). No es ℵ₀ (alef cero) y no es ℵ₁ (alef uno). No es ℵ₁ (alef uno) y si es ℵ₀ (alef cero).

Sea el conjunto A ⊆ ℕ, A = {n ∈ ℕ | n ≤ 10}, y sea A⁻ el cierre estricto de A con la operación "resta natural". A⁻ = ℤ. A⁻ = A. A⁻ = ℕ.

Sean L₁ y L₂ lenguajes sobre Σ. Si defino la operación "prefijos de L₁ sobre L₂", notado L₁ [ L₂, como L₁ [ L₂ = {w ∈ L₁ | w es prefijo de alguna palabra de L₂}, 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 ningún otro tipo. L(G) es del tipo 0, y puede ser del tipo 1, pero nunca del tipo 2.

Utilizando la biyección de la demostración de que ∑* es infinito numerable, si ∑₁ ⊆ ∑₂, y en los símbolos comunes coincide la ordenación, entonces el número de cadenas de ∑₁* y ∑₂* que tienen el mismo número asignado es. || ∑₁ ||. || ∑₁ || + 1. || ∑₁ || - 1.

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: 0. ||∑₁ ∩ ∑₂||. 1.

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

Dado el conjunto A = {a,b,c}, ¿con qué lenguaje se corresponde el cierre estricto de A con respecto a la operación concatenación?. L((a + b + c)*). L((a + b + c)(a + b + c)*). L(a* + b* + c*).

Si dos conjuntos A y B son equipotenciales, ¿cuál de las siguientes afirmaciones es FALSA?. Existe una función f : A -> B biyectiva. A es subconjunto 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.

¿Qué expresión de las siguientes NO se corresponde con un lenguaje?. ε. ∅. Σ⁺.

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.

Dada una gramática lineal G, entonces. G es a la vez lineal izquierda y lineal derecha. G es o bien lineal izquierda o bien lineal derecha. G puede no ser ni lineal izquierda ni lineal derecha.

Utilizando la biyección de la demostración de que Σ* es infinito numerable, si Σ = {a,b,c}, con esa ordenación, y w = aaaab, entonces: f(w) = 122. f(w) = 121. f(w) = 123.

Sea G = (N,T,P,S) con P = ∅. Entonces: L(G) ∈ L.3. G no genera ningún lenguaje. L(G) ∈ L.1 - L.2.

Si dos gramáticas G1 y G2 son equivalentes, entonces: Sus alfabetos terminales no son disjuntos. Sus alfabetos terminales son iguales. Sus alfabetos terminales pueden ser disjuntos.

Sea A un conjunto y R una relación tal que || R || = || A x A ||: R es una relación de equivalencia. R puede no ser transitiva. 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á?. 1. ||R||. ||A||.

Sean las gramáticas G1 = ({A}, {a}, {A -> Aa}, A) y G2 =({A}, {a}, {A -> aA}, A). Señala la afirmación INCORRECTA. L(G1) = L(G2) = {ε}. G1 y G2 son equivalentes. G1 y G2 son ambas lineales.

Dada una gramática lineal G, entonces: G es a la vez lineal izquierda y lineal derecha. G es o bien lineal izquierda o bien lineal derecha. G puede no ser ni lineal izquierda ni lineal derecha.