Copy and Edit

Teoria de Automatas (Curso Completo)

Description

Examen de febrero de la asignatura Teoría de Autómatas y Lenguajes Formales.
Daniel Alvarez Valero
Quiz by Daniel Alvarez Valero, updated more than 1 year ago
Daniel Alvarez Valero
Created by Daniel Alvarez Valero almost 11 years ago
460
1
0

Resource summary

Question 1

Question
Un AFD M...
Answer
  • decide si una cadena pertenece o no a L(M)
  • contiene infinitos estados
  • puede representar cualquier lenguaje de tipo 2

Question 2

Question
Respecto a la operación de unión de lenguajes:
Answer
  • los lenguajes sensibles al contexto no son cerrados
  • sólo son cerrados los lenguajes regulares y de contexto libre
  • los cinco tipos de lenguajes son cerrados

Question 3

Question
Si A={ 1,2,3} y B= {{1},{2,3}} entonces:
Answer
  • B es una partición de A
  • B es el conjunto potencia de A
  • B es un subconjunto de A

Question 4

Question
Si una GCL es recursiva por la izquierda, entonces
Answer
  • genera un lenguaje infinito
  • existe una gramática regular equivalente
  • existe una GCL equivalente que no es recursiva por la izquierda

Question 5

Question
Las expresiones regulares
Answer
  • pueden representar cualquier lenguaje representable
  • no pueden representar lenguajes que incluyan la cadena vacía
  • pueden representar cualquier lenguaje de tipo 3

Question 6

Question
La función Castor Afanoso es
Answer
  • una aplicación biyectiva entre naturales
  • parcialmente resoluble
  • creciente ( m > n

Question 7

Question
Un predicado es decidible
Answer
  • si es enumerable
  • sí y sólo si su función característica asociada es parcial
  • si se puede encontrar su valor de verdad cualesquiera que sean los argumentos

Question 8

Question
F(WHILE) es un conjunto con cardinal
Answer
  • igual al número de languajes no representables
  • infinito no numerable
  • igual que REC-TREC

Question 9

Question
Dado un lenguaje L:
Answer
  • L { ε } = L
  • L{ ε } = L∅
  • L{ ε } = ∅L

Question 10

Question
Si M es un AFDM entonces
Answer
  • todos los AFD equivalentes tienen menos estados finales que M
  • existe un AFD equivalente con menos estados que M
  • todos los AFD equivalentes tienen mayor o igual número de estados que M

Question 11

Question
Si un programa WHILE de tamaño 6 transita directamente de (5, 1, 1) a (2, 1,1), entonces su código
Answer
  • no contiene asignaciones a cero
  • contiene bucles
  • contiene seis asignaciones

Question 12

Question
De acuerdo con la clasificación de los lenguajes, se cumple que:
Answer
  • lenguajes de tipo 3 ⊂ lenguajes de tipo 0
  • lenguajes con estructura de frase ⊂ lenguajes de tipo 2
  • lenguajes lineales ⊂ lenguajes regulares

Question 13

Question
¿En cuál de los siguientes casos la gramática será del tipo "independiente del contexto"?
Answer
  • Si todas sus reglas son de tipo 1
  • Si al menos una de sus reglas es sensible al contexto
  • Si todas sus reglas son regulares terminales

Question 14

Question
Una gramática es
Answer
  • un algoritmo conclusivo para reconocer lenguajes
  • una forma de representar lenguajes
  • un subconjunto de L.REP

Question 15

Question
El cardinal de las funciones computables es:
Answer
  • menor que el de las funciones no calculables
  • mayor que el de las funciones representables
  • menor que el de las funciones totales

Question 16

Question
¿Cuál de las siguientes expresiones identifica un lenguaje sobre un alfabeto ?
Answer
  • ∥Σ∥
  • { Σ+}
  • ∅

Question 17

Question
Del Teorema de Equivalencia podemos concluir que:
Answer
  • existe un programa universal
  • REC = F(T-WHILE)
  • REC ⊆ F(WHILE)

Question 18

Question
El problema de la parada para programas con una entrada (dado por el predicado H 1 )
Answer
  • es parcialmente resoluble
  • ∈ TREC
  • es no enumerable

Question 19

Question
Un APND, con conjunto de estados finales F, acepta una cadena w si y sólo si
Answer
  • ∃ q ∈ F / ( s, ε, w ) ⊢ ( q, ε, ε )
  • ∃ q ∈ F / ( s, w, ε ) ⊢ ( q, ε, ε )
  • ∃ q ∈ F / ( s, w, ε ) ⊢* ( q, ε, ε )

Question 20

Question
Sean x e y cadenas sobre un alfabeto . Se cumple que xy = yx si:
Answer
  • x =xR e y =yR
  • =yR e y ≠ϵ
  • x = y

Question 21

Question
Si A ={1,2,3} entonces
Answer
  • 2^A ⊃ ∅
  • 2^A ⊃ {A}
  • 2^A ⊃ A^2

Question 22

Question
Si A={1,2} y B={3,4}, entonces R={(1,4), (2,3)}
Answer
  • es una función biyectiva de A a B
  • es una función parcial de A a B
  • no es una aplicación de A a B

Question 23

Question
La función reemplazar del programa universal (reem) es:
Answer
  • una función parcial de 3 argumentos
  • una función total
  • una función inyectiva

Question 24

Question
La gramática ( { A }, { a }, { A → Aa }, A )
Answer
  • representa el lenguaje L={ }
  • genera la derivación A -> Aa -> Aaa
  • es regular izquierda

Question 25

Question
Si un lenguaje cumple la condición de bombeo regular entonces
Answer
  • puede representarse con una expresión regular
  • no hay un AFD que lo represente
  • no podemos afirmar que es regular

Question 26

Question
Una Máquina de Turing de un estado sobre una cinta no vacía
Answer
  • no puede parar a más de dos posiciones del cuadrado escrutado inicial
  • puede parar sobre el cuadrado escrutado inicial
  • para con cualquier contenido de la cinta

Question 27

Question
Toda GCL que está en FNC cumple que
Answer
  • ninguna regla tiene en la parte derecha más de dos símbolos
  • ninguna regla tiene en la parte derecha menos de dos símbolos
  • todas las reglas tienen en la parte derecha exactamente dos símbolos

Question 28

Question
El AFD M=(K, , ,s, F) con K={ , } y ={0,1}, con la función de transición especificada por: δ(q 0 , 0) = q 1 , δ(q 0 , 1) = q 0 , δ(q 1 , 0) = q 1 , δ(q 1 , 1) = q 0 , y con s=q0 F=q1 representa:
Answer
  • un lenguaje con infinitas cadenas cuyo último símbolo es 0
  • un lenguaje con infinitas cadenas que no contienen 0
  • el conjunto vacío

Question 29

Question
La gramática G = ( {S}, {b}, { SS → bS }, S ) es
Answer
  • de tipo 1 y no es de tipo 2
  • de tipo 0 y no es de tipo 1
  • de tipo 2 y no es de tipo 3

Question 30

Question
Si A={1,2,3} y R={(1,1),(2,2)} entonces
Answer
  • R es una relación de equivalencia sobre A
  • R es una relación simétrica sobre A
  • R es una relación reflexiva sobre A

Question 31

Question
Una función de indexación para un conjunto de funciones tiene que ser:
Answer
  • sobreyectiva
  • inyectiva
  • biyectiva

Question 32

Question
Elija la opción correcta
Answer
  • ∥N∥ = 2^ℵ0
  • ∥R∥ − ∥N∥ = 2^ℵ0
  • ∥Q∥ = 2^ℵ0

Question 33

Question
L(AFD) =
Answer
  • L(APND)
  • L.2
  • L(AFND)

Question 34

Question
"Principia Mathematica" fue escrito por
Answer
  • Alfred N. Whitehead y Bertrand Russell
  • Stephen C. Kleene y Alonzo Church
  • Alan M. Turing

Question 35

Question
La gramática ( { A }, { a }, { A → Aa, A → aA }, A )
Answer
  • genera la derivación A -> Aa -> aAa
  • no es regular
  • representa el lenguaje { ε }

Question 36

Question
Una GCL es ambigua sii
Answer
  • ∃ w ∈ L(G) / w es producto de más de un árbol de derivación
  • ∀ w ∈ L(G) / w es producto de más de un árbol de derivación
  • ∀ w ∈ L(G) / w es producto de infinitos árboles de derivación

Question 37

Question
Sea Σ = {a,b,c}. Dado L = {w ∈ Σ* | aa no es una subcadena de w }, una ER del mismo es:
Answer
  • L = (b+c)* (a+ε) ( (b+c) (a+ε) )* (b+c)*
  • L=(b+c)* a ( (b+c) a )* (b+c)*
  • L=(b+c)* (a+ε) (b+c) (a+ε)

Question 38

Question
La función complejidad Temporal (T)
Answer
  • no puede calcularse cuando no es posible alcanzar una configuración terminal
  • para una entrada dada nos da el valor de la variable X1al final del proceso de cómputo, siempre que se alcance una configuración terminal
  • es una función total

Question 39

Question
Si M = ( {s,f}, {a,b}, {a,b}, {(( s, aa, ), (s, b)), (( s, , ), (f, )), (( f, a, b), (f, ))}, s, {f} ) entonces
Answer
  • L(M) = {wwwR ∣w ∈ {a,b} ∗ }
  • L(M) = {w ∈ {a,b} ∗ ∣w =a 3n con n ∈ ℕ}
  • L(M) = {wwR ∣w ∈ {a,b} ∗ }

Question 40

Question
σ(θ) es:
Answer
  • una recursión primitiva de funciones iniciales
  • una función recursiva parcial
  • una función constante

Question 41

Question
En el modelo de funciones recursivas, el símbolo Pi ( ) representa:
Answer
  • un conjunto finito de funciones
  • un subconjunto de TREC
  • una función inicial

Question 42

Question
Elija la opción correcta:
Answer
  • N^2 y N no son equipotenciales
  • N* y N son equipotenciales
  • existen tantos vectores de tres naturales como números naturales

Question 43

Question
Dados A ={1,2,3}, B= {4} y R={(1,4)}, se cumple que:
Answer
  • R es un subconjunto de A x B
  • R es una relación binaria sobre A
  • R es una relación de equivalencia sobre A

Question 44

Question
El cierre amplio de un conjunto para una operación
Answer
  • no incluye el conjunto vacío
  • no incluye el elemento neutro
  • incluye su cierre estricto

Question 45

Question
Dada una gramática G=(N,T,P,S), se cumple que:
Answer
  • N intersección T = Ø
  • N intersección T = S
  • N intersección T = V

Question 46

Question
Dada una gramática, el conjunto de reglas de producción P cumple que:
Answer
  • P = N interseccion T
  • P (N interseccion T)+ × (N interseccion T)*
  • P = (N interseccion T)*

Question 47

Question
Dada una gramática de tipo 2, siempre podemos responder si:
Answer
  • el lenguaje que representa es vacío
  • es equivalente a otra gramática de tipo 2
  • existe una gramática regular equivalente

Question 48

Question
El teorema de Myhill-Nerode suele usarse para:
Answer
  • demostrar que un lenguaje no es vacío
  • demostrar que un lenguaje es regular
  • demostrar que un lenguaje no es regular

Question 49

Question
Si en un lenguaje sobre todas sus cadenas son indistinguibles, entonces
Answer
  • L = sigma*
  • L = Ø
  • Los 2 anteriores
Show full summary Hide full summary

Want to create your own Quizzes for free with GoConqr? Learn more.

Similar

BIOLOGY B1 4
x_clairey_x
Key Shakespeare Facts
Andrea Leyden
Chemical Symbols
Keera
ICT Key Terms Quiz - Part 1
Mr Mckinlay
Of Mice and Men Quotes
_Jess_
Poppies - Jane Weir
Jessica Phillips
Rights and Responsibilities Flashcards - Edexcel GCSE Religious Studies Unit 8
nicolalennon12
Teaching Methods Every Educator Should Know
Micheal Heffernan
Using GoConqr to study geography
Sarah Egan
MAPA MENTAL DISEÑO GRAFICO
puntoideascali
Legislative Branch
Mr. Vakhovsky
Browse Library