Teoría de Autómatas (Parcial 1)

Question 1 of 19

Medal-premium 1

Sea Σ = {a,b,c,d}. Una Expresión Regular
para el lenguaje L = { w ∈ Σ* tal que |w| = n
|| Σ ||, n ≥ 0 } es:

Select one of the following:

  • ((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 of 19

Medal-premium 1

Marca la afirmación verdadera:

Select one of the following:

  • 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 of 19

Medal-premium 1

La regla a → a (donde a es un símbolo
terminal) es

Select one of the following:

  • 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 of 19

Medal-premium 1

Marca la afirmación verdadera:

Select one of the following:

  • Todo lenguaje regular es finito.

  • Todo lenguaje es numerable.

  • Todo lenguaje no representable es no
    numerable.

Question 5 of 19

Medal-premium 1

Si α y β son expresiones regulares sobre un
alfabeto, entonces:

Select one of the following:

  • α* (βα)* = (α+β)*

  • (αββ* )* = (α αβ)*

  • ( α + ∅ ) = ( ∅* α )

Question 6 of 19

Medal-premium 1

Sea G = (N, T, P, S) con N= {S ,A}, T=
{a,b}, P={ S → A | aSA | bSA, A → a | b}
¿Qué lenguaje genera?

Select one of the following:

  • 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 of 19

Medal-premium 1

¿Es posible que ∀L ⊆ Σ∗ se cumpla que
L = L^R ?

Select one of the following:

  • 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 of 19

Medal-premium 1

Si G = (N,T,P,S) es lineal izquierda y lineal
derecha a la vez, entonces

Select one of the following:

  • ||L(G)|| ≤ ||T||

  • ||L(G)|| ≤ ||P||

  • ||L(G)|| ≠ 0

Question 9 of 19

Medal-premium 1

Marca la afirmación falsa:

Select one of the following:

  • 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 of 19

Medal-premium 1

Si A y B son conjuntos no numerables,
entonces:

Select one of the following:

  • A – B puede ser numerable

  • A – B siempre es no numerable

  • A – B siempre es numerable

Question 11 of 19

Medal-premium 1

Marca la afirmación falsa:

Select one of the following:

  • 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 of 19

Medal-premium 1

Dada una gramática G=(N,T,P,S), se cumple
que:

Select one of the following:

  • N⋂T = V

  • N⋂T = ∅

  • N⋂T = S

Question 13 of 19

Medal-premium 1

Si G = (N,T,P,S) es regular izquierda y
regular derecha a la vez, entonces

Select one of the following:

  • ||L(G)|| ≤ ||T||

  • ||L(G)|| ≥ 1

  • ||L(G)|| = 0

Question 14 of 19

Medal-premium 1

¿Cuál de las siguientes expresiones identifica
un lenguaje sobre un alfabeto ?

Select one of the following:

  • ∥Σ∥

  • {Σ+ }

Question 15 of 19

Medal-premium 1

Sea R una relación sobre un conjunto .
R ∪ R^−1 es:

Select one of the following:

  • la relación identidad

  • el cierre simétrico de R

Question 16 of 19

Medal-premium 1

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?

Select one of the following:

  • Tipos 0, 1, 2, L y LD.

  • Tipos 0, 1, 2, L y LI.

  • Tipos 0, 1, 2, L, R.

Question 17 of 19

Medal-premium 1

La gramática ( { A }, { a }, { A → Aa }, A )

Select one of the following:

  • genera la derivación A ⇒ Aa ⇒ Aaa ⇒ aaa

  • es regular izquierda

  • representa el lenguaje L={ }

Question 18 of 19

Medal-premium 1

Sean x e y dos cadenas, entonces x · y

Select one of the following:

  • tiene longitud ≥ que la de x

  • es un conjunto infinito

  • contiene | x | × | y | símbolos

Question 19 of 19

Medal-premium 1

El cierre amplio de un conjunto para una
operación

Select one of the following:

  • incluye su cierre estricto

  • no incluye el elemento neutro

  • no incluye el conjunto vacío

Icon_fullscreen

Teoría de Autómatas (Parcial 1)

blorkszb
Quiz by , created almost 3 years ago

Primer examen de los temas 1-4

Eye 121
Pin 0
Balloon-left 0
Tags No tags specified
blorkszb
Created by blorkszb almost 3 years ago
Close