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 over 10 years ago
450
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

Acids and Bases
silviaod119
Maths Quiz
Andrea Leyden
Maths C4 Trig formulae (OCR MEI)
Zacchaeus Snape
Biology- Genes, Chromosomes and DNA
Laura Perry
FREQUENCY TABLES: MODE, MEDIAN AND MEAN
Elliot O'Leary
Religious Studies- Marriage and the family
Emma Samieh-Tucker
Physics 2
Peter Hoskins
regular preterite tense conjugation -ar verbs
Pamela Dentler
1PR101 2.test - Část 5.
Nikola Truong
1PR101 2.test - Část 10.
Nikola Truong
Diseño de Software
Verny Fernandez
Browse Library