Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado: La mquina de Turing opera cclicamente dado que:
Seleccione una respuesta.
a. Comienza por una palabra de entrada.
b. Al comienzo de un ciclo se parte de una determinada configuracin.
c. Una instruccin viene representada por un quntupla.
d. La cabeza puede leer y escribir en un mismo carcter.
Question2
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado: Sea el alfabeto ?= [0,1] y el autmata de la figura siquiente: Determine de cuantas
formas puede procesar la cadena 00101
Seleccione una respuesta.
a. El autmata puede procesar la cadena 00101 de 4 formas distintas
b. Slo existe un modo en que el autmata puede procesar la cadena 00101
c. Al procesar la cadena 00101, el ltimo estado visitado es iempre el
estado q3 o bien el estado q2.
d. El autmata puede procesar la cadena 00101 de tres formas distintas
Question3
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro
(4) opciones de respuesta (1, 2, 3, 4). Solo dos (2) de estas opciones responden correctamente a la
pregunta de acuerdo con la siguiente informacin.
Marque A si 1 y 2 son correctas.
Marque B si 1 y 3 son correctas.
Marque C si 2 y 4 son correctas.
Marque D si 3 y 4 son correctas.
Enunciado: Un ejemplo de Lenguaje es el conjunto de palndromos (cadenas que se leen igual
hacia adelante, que hacia atrs). Para el caso del alfabeto [ a, b] Es vlido afirmar:
1. Pueden ser cadenas vlidas como: [ ?, b. aa, bb, aba, abba, aaaa, babbab, baaab]
2. Las cadenas vlidas para ese alfabeto obedece a sus seis posibles combinaciones: [a, b, ab, ba, aa,
bb]
3. Este Lenguaje tiene cadenas infinitas
4. Este Lenguaje tiene cadenas finitas.
Seleccione una respuesta.
a. Marque A si 1 y 2 son correctas.
b. Marque B si 1 y 3 son correctas.
c. Marque C si 2 y 4 son correctas.
d. Marque D si 3 y 4 son correctas.
Question4
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (1, 2, 3, 4). Solo dos (2) de estas opciones responden correctamente a la pregunta de
acuerdo con la siguiente informacin.
Marque A si 1 y 2 son correctas.
Marque B si 1 y 3 son correctas.
Marque C si 2 y 4 son correctas.
Marque D si 3 y 4 son correctas.
Enunciado: Analice el siguiente autmata en sus propiedades de diseo y lenguaje que puede aceptar
y seleccione las opciones correctas.
1. Es Regular
2. Es un autmata finito determinista (AFD)
3. Es Regular y cualquier cadena contiene al menos un cero.
4. Es Regular e independiente del contexto por lo que contiene ms de un estado Halt
Seleccione una respuesta.
a. Marque A si 1 y 2 son correctas.
b. Marque B si 1 y 3 son correctas.
c. Marque C si 2 y 4 son correctas.
d. Marque D si 3 y 4 son correctas.
Question5
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta
Enunciado: Dada la siguiente gramtica, evale las afirmaciones dadas y seleccione la correcta.
Seleccione una respuesta.
a. Acepta la cadena vaca
b. Acepta la cadena xyz
c. Acepta la cadena xy
d. Una cadena vlida es xxyy
Question6
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta
Enunciado: En una Mquina de Turing la cabeza es de Lectura/Escritura debido a que:
Seleccione una respuesta.
a. La Cinta puede ser modificada en curso de ejecucin
b. La Cabeza se mueve en una sola direccin
c. No pasa repetidas veces sobre un mismo segmento.
d. Se lee un carcter en la cinta.
Question7
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado: En los lenguajes decidibles,las cadenas o palabras que se aceptan tienen caractersticas
como:
Seleccione una respuesta.
a. Las cadenas de un lenguaje decidible corresponden a procedimientos que terminan,
b. Las cadenas de un lenguaje decidible indican nicamente la falta de capacidad o
nulidad de la operacin .y sique siendo decidible el problema.
c. Las cadenas de un lenguaje decidible indican nicamente la veracidad o cierre de la
operacin .y sique siendo decidible el problema.
d. Las cadenas de un lenguaje decidible indican procedimientos inconclusos y
rechazados adems por una MT..
Question8
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado: Las operaciones que permiten los PDA son:
Seleccione una respuesta.
a. Unin y concatenacin
b. Cerradura de Kllene y Unin
c. Divisin por minimizacin.
d. No se permiten operaciones en los PDA.
Question9
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta
Enunciado:Para el siguiente Autmata Finito No Determinista: AFND = (E, Q, f, q1 , F) donde E =
[a,b],
F = [q4 ] y Q = [q1 , q2 , q 3, q4 ], identifique correctamente el Lenguaje que reconoce:
Seleccione una respuesta.
a. a (b * a | a * b ) b * tambin b (b * | a * ) a b *
b. a (b *| b a * b ) b * tambin a (b | a) * a b *
c. a (b * b | a * b ) a * tambin a (b * | a * ) b a *
d. a (b * ) a | b* tambin a (b | a) * b a *
Question10
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (1, 2, 3, 4). Solo dos (2) de estas opciones responden correctamente a la pregunta de
acuerdo con la siguiente informacin.
Marque A si 1 y 2 son correctas.
Marque B si 1 y 3 son correctas.
Marque C si 2 y 4 son correctas.
Marque D si 3 y 4 son correctas.
Enunciado: Se disea el siguiente Autmata Finito Deterministico (AFD) para el lenguaje de palabras
del alfabeto [a,b] que no tiene varias a's seguidas. Esta solucin es defectuosa porque.
1. Hay palabras como baa, que tiene a's seguidas y sin embargo son aceptadas por el AFD.
2. Tiene dos finales o de aceptacin q y q .
3. Hay palabras como ba, que no tienen a's seguidas y sin embargo no son aceptadas por el AFD.
4. Hay palabras como baba que no tienen a's seguidas y sin embargo son aceptadas por el AFD pero
que no pertenecen al alfabeto dado.
Seleccione una respuesta.
a. Marque A si 1 y 2 son correctas.
b. Marque B si 1 y 3 son correctas.
c. Marque C si 2 y 4 son correctas.
d. Marque D si 3 y 4 son correctas.
Question11
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (1, 2, 3, 4). Solo dos (2) de estas opciones responden correctamente a la pregunta de
acuerdo con la siguiente informacin.
Marque A si 1 y 2 son correctas.
Marque B si 1 y 3 son correctas.
Marque C si 2 y 4 son correctas.
Marque D si 3 y 4 son correctas.
Enunciado: Un lenguaje es considerado regular si cumple con unas condiciones, por lo cual podemos
afirmar que el lenguaje L es regular si y solo si: (Tenga en cuenta la jerarqua d elos lenguajes).
1. L es finito
2. L es la unin o la concatenacin de dos lenguajes regulares R1 y R2. L = R1 U R2.
3. L es un infinito.
4. L es la interseccin de dos lenguajes NO regulares R1 y R2. L = R1 n R2.
Seleccione una respuesta.
a. Marque A si 1 y 2 son correctas.
b. Marque B si 1 y 3 son correctas.
c. Marque C si 2 y 4 son correctas.
d. Marque D si 3 y 4 son correctas.
Question12
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado:Los problemas de Hilbert: Plantearon cuestiones como:
Seleccione una respuesta.
a. Cuestionar si las matemticas son exactas
b. Se cuestion si cada afirmacin matemtica se puede refutar.
c. Se cuestion si la matemtica soluciona problemas indecidibles.
d. Se cuestion si las matemticas son completas, consistentes y decidibles. De all se
plantearon otros problemas de discusin.
Question13
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (1, 2, 3, 4). Solo dos (2) de estas opciones responden correctamente a la pregunta de
acuerdo con la siguiente informacin.
Marque A si 1 y 2 son correctas.
Marque B si 1 y 3 son correctas.
Marque C si 2 y 4 son correctas.
Marque D si 3 y 4 son correctas.
Enunciado: Analice el siguiente autmata en sus propiedades de aceptar lenguajes y determine que
cadenas acepta:
1. Si una cadena tiene menos de 5 unos, entonces tiene un nmero par de unos.
2. Si una cadena tiene 5 unos o ms, entonces contiene un nmero par de unos
[Link] una cadena tiene 5 unos o ms, entonces contiene un nmero impar de unos
4. Todas las cadenas que tengan igual nmero de unos y de ceros son aceptadas.
Seleccione una respuesta.
a. Marque A si 1 y 2 son correctas.
b. Marque B si 1 y 3 son correctas.
c. Marque C si 2 y 4 son correctas.
d. Marque D si 3 y 4 son correctas.
Question14
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta
Enunciado: El principal factor determinante de la profunda revolucin experimentada en el mbito de
la ciencia, la tcnica y la cultura de nuestros das, es el desarrollo de:
Seleccione una respuesta.
a. La Informtica
b. La Cultura
c. La Matemtica
d. La Ciencia
Question15
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro
(4) opciones de respuesta (1, 2, 3, 4). Solo dos (2) de estas opciones responden correctamente a la
pregunta de acuerdo con la siguiente informacin.
Marque A si 1 y 2 son correctas.
Marque B si 1 y 3 son correctas.
Marque C si 2 y 4 son correctas.
Marque D si 3 y 4 son correctas.
Enunciado: Mquina de Turing (MT) de dos direcciones: Una Mquina de Turing con una cinta infinita
en un sentido puede simular una Mquina de Turing con la cinta infinita en los dos sentidos.
Sea M una Mquina de Turing con una cinta infinita en los dos sentidos, entonces: (Analice primero si
es multicinta, multipista o de una sola cinta).
Para que se logre o se d esta mquina se debe cumplir:
1. La Mquina de Turing M que tiene una Cinta Infinita en un sentido, puede simular a M si tiene una
cinta con dos pistas.
2. La cinta superior contiene informacin correspondiente a la parte derecha de la cinta M a partir de
un punto de referencia dado.
3. La pista inferior contiene la parte izquierda y derecha de la cinta M (en orden inverso).
4. La pista inferior y superior leen los datos simultneamente en ambos sentidos. Luego y
dependiendo de los estado repetitivos, se detiene una pista y contina la que menos celdas tenga
ocupada.
Seleccione una respuesta.
a. Marque A si 1 y 2 son correctas.
b. Marque B si 1 y 3 son correctas.
c. Marque C si 2 y 4 son correctas.
d. Marque D si 3 y 4 son correctas.
Question16
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado: Sea el alfabeto ?= [0,1] y el autmata de la figura siquiente: Determine la Expresin
Regular (ER) que mejor lo representa:
Seleccione una respuesta.
a. 0*1*(01)
b. 0*1
c. (0+1)*01
d. (0*1)01
Question17
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta
Enunciado: Sea el lenguaje L de palabras formadas por a y b, pero que empiezan con a, como aab,
ab, a, abaa, etc.
Si analizamos el ejemplo y buscamos la solucin, cul sera la concatenacin de ese ejercicio.
Seleccione una respuesta.
a. [a][a, b]*
b. [c][a, b]*
c. [d][a, b]*
d. [q][a, b]*
Question18
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado: El estado general de un autmata de pilas est dado por:
Seleccione una respuesta.
a. El estado futuro y lo que falta por leer o procesar.
b. El estado inicial o de partida y el estado Final
c. El estado futuro, y la Pila.
d. El estado en que se encuentra, Lo que falta por leer y la Pila
Question19
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta
Enunciado: Los autmata finito no deterministicos (AFND) es una quntupla donde todos los
componentes son como en los AFDs, estos autmatas aceptan exactamente los mismo lenguajes que
los autmatas deterministicos, pero cuentan con una diferencia con relacin a los AFD como es:
Seleccione una respuesta.
a. El Estado inicial
b. El Alfabeto de entrada
c. El Conjunto finito de estados
d. La funcin de transicin
Question20
Puntos: 1
Contexto: Este tipo de pregunta se desarrolla en torno a un (1) enunciado y cuatro (4) opciones de
respuesta (A, B, C, D). Solo una (1) de estas opciones responde correctamente a la pregunta.
Enunciado: Respecto a las Mquinas de Turing, se afirma qe:
Seleccione una respuesta.
a. Una mquina de Turing universal es aqulla capaz de decidir cualquier lenguaje.
b. La MT se detiene (estado halt) (estado final) . Cuando queremos que una palabra
no sea aceptada, desde luego debemos evitar que la MT llegue al halt
c. Una mquina de Turing universal es aqulla capaz de implementar cualquier
funcin.
d. Al disear una MT que acepte un cierto lenguaje, en realidad diseamos un
Algoritmo o un autmata que controla la cabeza y la cinta, el cual es un autmata
sin salida por la capacidad de proceso que tiene
