8/13/2019 Act 5 quiz 1 20.8 de 25

1/10

Act 5: Quiz 1 - Unidad No. 1

Revisin del intento 1

Comenzado el: lunes, 1 de abril de 2013, 19:43

Completado el: lunes, 1 de abril de 2013, 20:38

Tiempo empleado: 54 minutos 34 segundos

Continuar

1

Una de las siguientes afirmaciones NOaplica a los lenguajes que reconocen un autmata. Identifquela

Seleccione una respuesta.

a. Un automata finito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la

coleccion de cadenas de dicho lenguaje.

b. Dada una gramatica regular G, siempre existe un automata finito M tal que L(G) = L(M) y

M tiene un unico estado de aceptacion.

c. Un automata reconoce una cadena cuando alcanza un estado de aceptacion durante su

lectura

d. Un automata finito determinista utilizado como reconocedor de lenguajes con al menos una

cadena necesariamente tiene que tener al menos un estado de aceptacion.

2

Las condiciones mnimas para poder describir un Autmata Finito Determinstico (DFA) son:

8/13/2019 Act 5 quiz 1 20.8 de 25

2/10

Seleccione al menos una respuesta.

a. Identificando el alfabeto

b. Identificando el estado inicial y los estados finale

c. Identificando la funcin de transicin.

d. Dando la lista de sus estados.

3

En cuanto a los lenguajes formales, relacione correctamente las siguientes afirmaciones y su significado.

Posible Alfabeto {0,1}

El alfabeto Es un conjunto finito

Cadena sobre un alfabeto 010110

La palabra vaca Cadena de Longitud cero

4Un alfabeto es un conjunto finito de smbolos. De esta definicin podemos afirmar correctamente:(Seleccione dos de las afirmaciones que sean correctas).

Seleccione al menos una respuesta.

8/13/2019 Act 5 quiz 1 20.8 de 25

3/10

a. Dado un alfabeto, podemos formar palabras o cadenas con los smbolos del

alfabeto

b. Por smbolo no se est haciendo referencia a un slo carcter. Los smbolos

pueden ser nombres.

c. Las cadenas que se forman a partir de un alfabeto finito, resultan ser infinitas.

d. Por ser un alfabeto un conjunto finito de elementos, las posibles cadenas que se

formen no pueden ser vacas

5

Uno de los principales factores determinantes en la revolucin en el mbito de la ciencia, la tcnica y lacultura de nuestros das es el desarrollo de la Informtica PORQUEUn lenguaje natural como el ingls o el

espaol son la clase de lenguajes que han evoucionado con el paso del tiempo y tienen por fin lacomunicacin humana.

Seleccione una respuesta.

a. La Afirmacin es FALSA, pero la Razn es una proposicin VERDADERA

b. La Afirmacin y la Razn son VERDADERAS y la Razn es una explicacin CORRECTA

de la Afirmacin

c. La Afirmacin es VERDADERA, pero la Razn es una proposicin FALSA

d. La Afirmacin y la Razn son VERDADERAS pero la Razn NO es una explicacin

CORRECTA de la Afirmacin

8/13/2019 Act 5 quiz 1 20.8 de 25

4/10

6

Para comprender la definicin de Autmata Finito, se suele asociar el concepto al de una Mquina que evoca un aparato metlico usualmenteruidoso, mecnico y que ejecuta tareas repetitivas que requieren de mucha fuerza o velocidad combinadas con precisin. Cuales

seran caractersticas de los Autmatas Finitos:

Seleccione al menos una respuesta.

Seleccione al menos una respuesta.

a. Los autmatas finitos son capaces de reconocer solamente un determinado tipo de

lenguajes, llamados lenguajes Regulares.

b. Las mquinas de Turing y los autmatas de pila son autmatas finitos.

c. Los autmatas finitos solo pueden aceptar lenguajes finitos.

d. Los autmatas finitos tienen un nmero finito de estados.

7

Indique cual de las siguientes afirmaciones aplica correctamente a las caractersticas o definicones de unAF.

Seleccione una respuesta.

a. Un automata finito no determinista es una representacion abreviada de un automata finito

determinista.

8/13/2019 Act 5 quiz 1 20.8 de 25

5/10

b. En un diagrama completo que represente a un automata finito determinista, de cada estado

sale un arco por simbolo y solo uno.

c. Los automatas finitos no deterministas son mas potentes que los automatas finitos

deterministasd. Ninguna de las afirmaciones anteriores es cierta

8

Un Autmata Determinstico de estados finitos (DFA), M, es una quntupla: (Q, , q i, F, ), donde:

Q es un conjunto finito de estados. es un alfabeto finito.

qi

Q es el estado inicial.F Q son los estados finales. : (Q ) Q es la funcin de transicin de estados.

La condicin de ser Determinstico es debido a que:

Seleccione al menos una respuesta.

a. En cada instante lee un smbolo y dependiendo del smbolo y del estado s en el que se

encuentra, cambia al estado dado por la funcin de transicin: (s, )

b. Las transacciones estn descritas por una funcin total.

c. Hay un nico estado inicial.

8/13/2019 Act 5 quiz 1 20.8 de 25

6/10

d. El autmata comienza en el estado inicial y lee una secuencia de smbolos (smbolo por

smbolo hasta que se acabe la secuencia).

9Los Automatas finitos no Deterministicos tienen las caracteristicas de:

Seleccione al menos una respuesta.

a. Las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra

vacia.

b. Las transiciones no tengan como etiqueta palabras de varias letras o hasta la palabra

vacia.

c. No permitir que cada nodo del diagrama de estados salga un numero de flechasmayor o menor.

d. Permitir que de cada nodo del diagrama de estados salga un numero de flechasmayor o menor.

10

Acorde a al historia y a lo que se dice de los modelos de computacin, las Mquinas de Turing (MT), comomquinas reconocedoras de los lenguajes formales dependientes del contexto o estructurado por frases,surgieron hace: (seleccione una opcion valida)

Seleccione una respuesta.

a. En 1970

8/13/2019 Act 5 quiz 1 20.8 de 25

7/10

b. Hace 5 aos

c. Hace 50 aos

d. Hace 20 aos

11

Los tems que encontrar a continuacin constan de una afirmacin VERDADERA (tesis) y dos postuladostambin VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si lospostulados se deducen lgicamente de la afirmacin y seleccionar la respuesta en su hoja de cotejo,conforme a la siguiente instruccin:

Marque A si de la tesis se deducen los postulados I y II.Marque B si de la tesis se deduce el postulado I.Marque C si de la tesis slo se deduce el postulado II.Marque D si ninguno de los postulados se deduce de la tesis.

TESIS. Los autmatas finitos determinsticos (AFD) son un subconjunto propio de los no determinsticos(AFN).

POSTULADO I. Todo AFD es un AFN

POSTULADO II. Se puede pensar entonces que los AFN son ms poderosos que los AFD, en el sentidode que habra algunos lenguajes aceptados por algn AFN para los cuales no hay ningn AFD que losacepte

8/13/2019 Act 5 quiz 1 20.8 de 25

8/10

Seleccione una respuesta.

a. OPCION B

b. OPCION C

c. OPCION D

d. OPCION A

12

Los palindromos (palabras capicuas) del idioma castellano, tales como "a", "y", "dad", "oso", "erre", etc.,constituyen un:

Seleccione una respuesta.

a. Lenguaje estructurado por frases (en sentido estricto)

b. Lenguaje independiente del contexto (en sentido estricto)

c. Lenguaje regular

d. Es una maquina de turing.

13

Un ejemplo de Lenguaje es el conjunto de palndromos (cadenas que se leen igual hacia adelante, quehacia atrs). Para el caso del alfabeto { 0, 1} Es vlido afirmar: (Seleccione dos respuestas).

8/13/2019 Act 5 quiz 1 20.8 de 25

9/10

Tenga en cuenta que el smbolo lambda (usado en autmatas), http://es.wikipedia.org/wiki/Lambda

Seleccione al menos una respuesta.

a. Este Lenguaje tiene cadenas infinitas

b. Pueden ser cadenas vlidas como: {lambda, 0, 1. 00, 11, 010, 0110, 000000, 101101,

10001}

c. Las cadenas vlidas para ese alfabeto obedece a sus seis posibles combinaciones: {0, 1, 01,

10, 00, 11}

d. Este Lenguaje tiene cadenas finitas

14

Los autmatas finitos no Determinsticos o no deterministas tienen las caractersticas de:

Seleccione al menos una respuesta

Seleccione al menos una respuesta.

a. Las transiciones no tengan como etiqueta palabras de varias letras o hasta la palabra

vaca.

b. Permitir que de cada nodo del diagrama de estados salga un nmero de flechas

mayor o menor

8/13/2019 Act 5 quiz 1 20.8 de 25

10/10

c. No permitir que de cada nodo del diagrama de estados salga un nmero de flechas

mayor o menor

d. Las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra

vaca.

15

En un contexto general un Lenguaje lo podemos definir como:

Seleccione una respuesta.

a. Conjunto de instrucciones que indican acciones a realizar

b. Significado de las cadenas que lo componen

c. Estudio de las reglas y principios que regulan su uso

d. Un Sistema de Smbolos Convencionales, hablados o escritos con el que nos comunicamos