Daniel Alvarez Valero
Quiz por , criado more than 1 year ago

Primer examen de los temas 1-4

153
0
0
Daniel Alvarez Valero
Criado por Daniel Alvarez Valero quase 11 anos atrás
Fechar

Teoría de Autómatas (Parcial 1)

Questão 1 de 19

1

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

Selecione uma das seguintes:

  • ((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))*

Explicação

Questão 2 de 19

1

Marca la afirmación verdadera:

Selecione uma das seguintes:

  • 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

Explicação

Questão 3 de 19

1

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

Selecione uma das seguintes:

  • 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

Explicação

Questão 4 de 19

1

Marca la afirmación verdadera:

Selecione uma das seguintes:

  • Todo lenguaje regular es finito.

  • Todo lenguaje es numerable.

  • Todo lenguaje no representable es no
    numerable.

Explicação

Questão 5 de 19

1

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

Selecione uma das seguintes:

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

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

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

Explicação

Questão 6 de 19

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?

Selecione uma das seguintes:

  • 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 }

Explicação

Questão 7 de 19

1

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

Selecione uma das seguintes:

  • Sí, cuando el cardinal de Σ es dos.

  • Sí, cuando el cardinal de Σ es uno.

  • No, ya que el cardinal de Σ no puede ser
    cero.

Explicação

Questão 8 de 19

1

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

Selecione uma das seguintes:

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

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

  • ||L(G)|| ≠ 0

Explicação

Questão 9 de 19

1

Marca la afirmación falsa:

Selecione uma das seguintes:

  • La regla ABA→BABA es sensible al
    contexto.

  • La regla AA → BB es de tipo uno.

  • La regla ABA→BBA es sensible al
    contexto

Explicação

Questão 10 de 19

1

Si A y B son conjuntos no numerables,
entonces:

Selecione uma das seguintes:

  • A – B puede ser numerable

  • A – B siempre es no numerable

  • A – B siempre es numerable

Explicação

Questão 11 de 19

1

Marca la afirmación falsa:

Selecione uma das seguintes:

  • 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.

Explicação

Questão 12 de 19

1

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

Selecione uma das seguintes:

  • N⋂T = V

  • N⋂T = ∅

  • N⋂T = S

Explicação

Questão 13 de 19

1

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

Selecione uma das seguintes:

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

  • ||L(G)|| ≥ 1

  • ||L(G)|| = 0

Explicação

Questão 14 de 19

1

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

Selecione uma das seguintes:

  • ∥Σ∥

  • {Σ+ }

Explicação

Questão 15 de 19

1

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

Selecione uma das seguintes:

  • la relación identidad

  • el cierre simétrico de R

Explicação

Questão 16 de 19

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?

Selecione uma das seguintes:

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

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

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

Explicação

Questão 17 de 19

1

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

Selecione uma das seguintes:

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

  • es regular izquierda

  • representa el lenguaje L={ }

Explicação

Questão 18 de 19

1

Sean x e y dos cadenas, entonces x · y

Selecione uma das seguintes:

  • tiene longitud ≥ que la de x

  • es un conjunto infinito

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

Explicação

Questão 19 de 19

1

El cierre amplio de un conjunto para una
operación

Selecione uma das seguintes:

  • incluye su cierre estricto

  • no incluye el elemento neutro

  • no incluye el conjunto vacío

Explicação