446548
Description
Quiz by Daniel Alvarez Valero, updated more than 1 year ago
|
Created by Daniel Alvarez Valero
almost 11 years ago
|
|
Question 1
Question
Sea Σ = {a,b,c,d}. Una Expresión Regular
para el lenguaje L = { w ∈ Σ* tal que |w| = n
|| Σ ||, n ≥ 0 } es:
Answer
-
((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))*
Question 2
Question
Marca la afirmación verdadera:
Answer
-
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
Question 3
Question
La regla a → a (donde a es un símbolo
terminal) es
Answer
-
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
Question 4
Question
Marca la afirmación verdadera:
Answer
-
Todo lenguaje regular es finito.
-
Todo lenguaje es numerable.
-
Todo lenguaje no representable es no numerable.
Question 5
Question
Si α y β son expresiones regulares sobre un
alfabeto, entonces:
Answer
-
α* (βα)* = (α+β)*
-
(αββ* )* = (α αβ)*
-
( α + ∅ ) = ( ∅* α )
Question 6
Question
Sea G = (N, T, P, S) con N= {S ,A}, T=
{a,b}, P={ S → A | aSA | bSA, A → a | b}
¿Qué lenguaje genera?
Answer
-
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 }
Question 7
Question
¿Es posible que ∀L ⊆ Σ∗ se cumpla que
L = L^R ?
Answer
-
Sí, cuando el cardinal de Σ es dos.
-
Sí, cuando el cardinal de Σ es uno.
-
No, ya que el cardinal de Σ no puede ser cero.
Question 8
Question
Si G = (N,T,P,S) es lineal izquierda y lineal
derecha a la vez, entonces
Answer
-
||L(G)|| ≤ ||T||
-
||L(G)|| ≤ ||P||
-
||L(G)|| ≠ 0
Question 9
Question
Marca la afirmación falsa:
Answer
-
La regla ABA→BABA es sensible al contexto.
-
La regla AA → BB es de tipo uno.
-
La regla ABA→BBA es sensible al contexto
Question 10
Question
Si A y B son conjuntos no numerables,
entonces:
Answer
-
A – B puede ser numerable
-
A – B siempre es no numerable
-
A – B siempre es numerable
Question 11
Question
Marca la afirmación falsa:
Answer
-
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.
Question 12
Question
Dada una gramática G=(N,T,P,S), se cumple
que:
Answer
-
N⋂T = V
-
N⋂T = ∅
-
N⋂T = S
Question 13
Question
Si G = (N,T,P,S) es regular izquierda y
regular derecha a la vez, entonces
Answer
-
||L(G)|| ≤ ||T||
-
||L(G)|| ≥ 1
-
||L(G)|| = 0
Question 14
Question
¿Cuál de las siguientes expresiones identifica
un lenguaje sobre un alfabeto ?
Answer
-
∥Σ∥
-
{Σ+ }
-
∅
Question 15
Question
Sea R una relación sobre un conjunto .
R ∪ R^−1 es:
Answer
-
la relación identidad
-
∅
-
el cierre simétrico de R
Question 16
Question
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?
Answer
-
Tipos 0, 1, 2, L y LD.
-
Tipos 0, 1, 2, L y LI.
-
Tipos 0, 1, 2, L, R.
Question 17
Question
La gramática ( { A }, { a }, { A → Aa }, A )
Answer
-
genera la derivación A ⇒ Aa ⇒ Aaa ⇒ aaa
-
es regular izquierda
-
representa el lenguaje L={ }
Question 18
Question
Sean x e y dos cadenas, entonces x · y
Answer
-
tiene longitud ≥ que la de x
-
es un conjunto infinito
-
contiene | x | × | y | símbolos
Question 19
Question
El cierre amplio de un conjunto para una
operación
Answer
-
incluye su cierre estricto
-
no incluye el elemento neutro
-
no incluye el conjunto vacío
Want to create your own Quizzes for free with GoConqr? Learn more.