Test
Teoría de Autómatas (Parcial 1)
Preguntas del test (19)
1Sea Σ = {a,b,c,d}. Una Expresión Regular
para el lenguaje L = { w ∈ Σ* tal que |w| = n
|| Σ ||, n ≥ 0 } es:- A((a+b+c+d))*
- B((a+b+c+d)(a+b+c+d)(a+b+c+d))*
- C((a+b+c+d)(a+b+c+d)(a+b+c+d)
(a+b+c+d))*
2Marca la afirmación verdadera:
- AEl complementario de un lenguaje no
representable puede ser representable - BTodo lenguaje no representable es no
numerable - CTodo lenguaje no representable es la
unión de infinitos lenguajes
representables
- AEl complementario de un lenguaje no
3La regla a → a (donde a es un símbolo
terminal) es- Ade tipo 2 y no es de tipo 3
- Bde tipo 0 y no es de tipo 1
- Cde tipo 1 y no es de tipo 2
4Marca la afirmación verdadera:
- ATodo lenguaje regular es finito.
- BTodo lenguaje es numerable.
- CTodo lenguaje no representable es no
numerable.
5Si α y β son expresiones regulares sobre un
alfabeto, entonces:- Aα* (βα)* = (α+β)*
- B(αββ* )* = (α αβ)*
- C( α + ∅ ) = ( ∅* α )
6Sea G = (N, T, P, S) con N= {S ,A}, T=
{a,b}, P={ S → A | aSA | bSA, A → a | b}
¿Qué lenguaje genera?- AL(G) = { w ∈ T* tal que w = a^n b^n , con n
≥ 0 } - BL(G) = {w ∈ T* tal que | | = 2n, con n
≥ 0 } - CL(G) = { w ∈ T* tal que | | = 2n+1, con
n ≥ 0 }
- AL(G) = { w ∈ T* tal que w = a^n b^n , con n
7¿Es posible que ∀L ⊆ Σ∗ se cumpla que
L = L^R ?- ASí, cuando el cardinal de Σ es dos.
- BSí, cuando el cardinal de Σ es uno.
- CNo, ya que el cardinal de Σ no puede ser
cero.
8Si G = (N,T,P,S) es lineal izquierda y lineal
derecha a la vez, entonces- A||L(G)|| ≤ ||T||
- B||L(G)|| ≤ ||P||
- C||L(G)|| ≠ 0
9Marca la afirmación falsa:
- ALa regla ABA→BABA es sensible al
contexto. - BLa regla AA → BB es de tipo uno.
- CLa regla ABA→BBA es sensible al
contexto
- ALa regla ABA→BABA es sensible al
10Si A y B son conjuntos no numerables,
entonces:- AA – B puede ser numerable
- BA – B siempre es no numerable
- CA – B siempre es numerable
11Marca la afirmación falsa:
- ASólo los lenguajes finitos pueden ser
representados por una expresión regular. - BTodas las gramáticas regulares generan
lenguajes que son representables
mediante expresiones regulares. - CNo todo lenguaje representable puede
ser representado por una expresión
regular.
- ASólo los lenguajes finitos pueden ser
12Dada una gramática G=(N,T,P,S), se cumple
que:- AN⋂T = V
- BN⋂T = ∅
- CN⋂T = S
13Si G = (N,T,P,S) es regular izquierda y
regular derecha a la vez, entonces- A||L(G)|| ≤ ||T||
- B||L(G)|| ≥ 1
- C||L(G)|| = 0
14¿Cuál de las siguientes expresiones identifica
un lenguaje sobre un alfabeto ?- A∥Σ∥
- B{Σ+ }
- C∅
15Sea R una relación sobre un conjunto .
R ∪ R^−1 es:- Ala relación identidad
- B∅
- Cel cierre simétrico de R
16Sea 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?- ATipos 0, 1, 2, L y LD.
- BTipos 0, 1, 2, L y LI.
- CTipos 0, 1, 2, L, R.
17La gramática ( { A }, { a }, { A → Aa }, A )
- Agenera la derivación A ⇒ Aa ⇒ Aaa ⇒ aaa
- Bes regular izquierda
- Crepresenta el lenguaje L={ }
18Sean x e y dos cadenas, entonces x · y
- Atiene longitud ≥ que la de x
- Bes un conjunto infinito
- Ccontiene | x | × | y | símbolos
19El cierre amplio de un conjunto para una
operación- Aincluye su cierre estricto
- Bno incluye el elemento neutro
- Cno incluye el conjunto vacío
Información
- Descripción
- Primer examen de los temas 1-4
- Idioma
- Español
- Visitas
- 180
- Historial
- Creado el 17 dic 2013 · actualizado el 23 jun 2016
- Etiquetas
- Valoración
- Aún sin valoraciones Valora este test