Sea Σ = {a,b,c,d}. Una Expresión Regular para el lenguaje L = { w ∈ Σ* tal que |w| = n || Σ ||, n ≥ 0 } es:
((a+b+c+d))*
((a+b+c+d)(a+b+c+d)(a+b+c+d))*
((a+b+c+d)(a+b+c+d)(a+b+c+d) (a+b+c+d))*
Marca la afirmación verdadera:
El complementario de un lenguaje no representable puede ser representable
Todo lenguaje no representable es no numerable
Todo lenguaje no representable es la unión de infinitos lenguajes representables
La regla a → a (donde a es un símbolo terminal) es
de tipo 2 y no es de tipo 3
de tipo 0 y no es de tipo 1
de tipo 1 y no es de tipo 2
Todo lenguaje regular es finito.
Todo lenguaje es numerable.
Todo lenguaje no representable es no numerable.
Si α y β son expresiones regulares sobre un alfabeto, entonces:
α* (βα)* = (α+β)*
(αββ* )* = (α αβ)*
( α + ∅ ) = ( ∅* α )
Sea G = (N, T, P, S) con N= {S ,A}, T= {a,b}, P={ S → A | aSA | bSA, A → a | b} ¿Qué lenguaje genera?
L(G) = { w ∈ T* tal que w = a^n b^n , con n ≥ 0 }
L(G) = {w ∈ T* tal que | | = 2n, con n ≥ 0 }
L(G) = { w ∈ T* tal que | | = 2n+1, con n ≥ 0 }
¿Es posible que ∀L ⊆ Σ∗ se cumpla que L = L^R ?
Sí, cuando el cardinal de Σ es dos.
Sí, cuando el cardinal de Σ es uno.
No, ya que el cardinal de Σ no puede ser cero.
Si G = (N,T,P,S) es lineal izquierda y lineal derecha a la vez, entonces
||L(G)|| ≤ ||T||
||L(G)|| ≤ ||P||
||L(G)|| ≠ 0
Marca la afirmación falsa:
La regla ABA→BABA es sensible al contexto.
La regla AA → BB es de tipo uno.
La regla ABA→BBA es sensible al contexto
Si A y B son conjuntos no numerables, entonces:
A – B puede ser numerable
A – B siempre es no numerable
A – B siempre es numerable
Sólo los lenguajes finitos pueden ser representados por una expresión regular.
Todas las gramáticas regulares generan lenguajes que son representables mediante expresiones regulares.
No todo lenguaje representable puede ser representado por una expresión regular.
Dada una gramática G=(N,T,P,S), se cumple que:
N⋂T = V
N⋂T = ∅
N⋂T = S
Si G = (N,T,P,S) es regular izquierda y regular derecha a la vez, entonces
||L(G)|| ≥ 1
||L(G)|| = 0
¿Cuál de las siguientes expresiones identifica un lenguaje sobre un alfabeto ?
∥Σ∥
{Σ+ }
∅
Sea R una relación sobre un conjunto . R ∪ R^−1 es:
la relación identidad
el cierre simétrico de R
Sea G = (N,T,P,S) con N={A, B}, T={0, 1}, P={ A → 1100A | 0B | 0, B → 0B | 0}, S=A. ¿De qué tipos (0, 1, 2, RI, RD, L, LI, LD) es la gramática?
Tipos 0, 1, 2, L y LD.
Tipos 0, 1, 2, L y LI.
Tipos 0, 1, 2, L, R.
La gramática ( { A }, { a }, { A → Aa }, A )
genera la derivación A ⇒ Aa ⇒ Aaa ⇒ aaa
es regular izquierda
representa el lenguaje L={ }
Sean x e y dos cadenas, entonces x · y
tiene longitud ≥ que la de x
es un conjunto infinito
contiene | x | × | y | símbolos
El cierre amplio de un conjunto para una operación
incluye su cierre estricto
no incluye el elemento neutro
no incluye el conjunto vacío
