Act 5

Act 5: Quiz 1 - Unidad No. 1

Revisión del intento 1

Comenzado el: miércoles, 3 de abril de 2013, 20:28

Completado el: miércoles, 3 de abril de 2013, 21:22

Tiempo empleado: 54 minutos 20 segundos

Puntuación bruta: 6.75/15 (45 %)

Calificación: de un máximo de

Comentario - Contesto parcialmente

1Puntos: 1

Indicar cuál es el tipo de autómata más sencillo (menos potente) capaz de reconocer el lenguaje {xnymzn | n>=25, m>=50}.

Seleccione una respuesta.

a. Un autómata de pila determinista

b. Un autómata de pila no determinista

c. Un autómata finito

d. Una máquina de Turing. Incorrecto

IncorrectoPuntos para este envío: 0/1.

2Puntos: 1

El nombre "finito" en un Autómata, se justifica por una de las siguientes afirmaciones. Seleccione una.


a. Que el Autómata tiene un solo estado Inicial que se puede representar por un * o por un círculo doble.

b. Del hecho que el Autómata almacena información en un solo estado (el final), que es donde termina su recorrido

c. Que el Autómata contiene un alfabeto símbolos (letras del abecedario) y estas son finitas.

Incorrecto. Esta definición no aplica a la concepción de "finito" en un autómata.

d. Del hecho que el autómata solo tiene un conjunto finito de estados distintos para recordar lo procesado (no tiene ningún sistema de

Continuar

almacenamiento de información adicional)


Al describir una máquina de estados finitos en particular, debemos incluir las informaciones que varían de un autómata a otro; es decir, no tiene sentido incluir descripciones generales aplicables a todo autómata. Estas informaciones son exactamente las que aparecen en un diagrama de estados y transiciones.

3Puntos: 1

El numero minimo de estados de un AFND (automata finito no determinista) es de:


a. Uno

b. Dos

c. No hay numero minimo

d. Depende del alfabeto sobre el que esta definido.


4Puntos: 1

Los Automatas finitos no Deterministicos tienen las caracteristicas de:

Seleccione al menos una respuesta.

a. Permitir que de cada nodo del diagrama de estados salga un numero de flechas mayor o menor.

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

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

d. No permitir que cada nodo del diagrama de estados salga un numero de flechas mayor o menor.

CorrectoPuntos para este envío: 1/1.

5Puntos: 1

Los autómatas finitos se utilizan generalmente para:


a. Como un analizador en la traducción de algoritmos al computador.

Respuesta Correcta

b. No tienen un uso habitual en la computación práctica actual.

c. Verificar que las cadenas pertenecen al lenguaje Respuesta Correcta

d. Reconocer todo tipo de lenguajes


6Puntos: 1

Una de las siguientes afirmaciones NO aplica a los lenguajes que reconocen un autómata. Identifíquela


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

b. Un automata finito determinista utilizado como reconocedor de lenguajes con al menos una cadena necesariamente tiene que tener al menos un estado de aceptacion.

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

d. Un automata finito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la coleccion de cadenas de dicho lenguaje.


7Puntos: 1

Los ítems que encontrará a continuación constan de una afirmación VERDADERA (tesis) y dos postulados también VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si los postulados se deducen lógicamente de la afirmación y seleccionar la respuesta en su hoja de cotejo, conforme a la siguiente instrucción:

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 sólo se deduce el postulado II.Marque D si ninguno de los postulados se deduce de la tesis.

TESIS: El estado de un autómata es toda la información necesaria en un momento dado, para poder deducir, dado un símbolo de entrada en ese momento, cuál será el símbolo de salida.

POSTULADO I: Conocer el estado de un autómata, es lo mismo que conocer toda la historia de símbolos de entrada, así como el estado inicial, estado en que se encontraba el autómata al recibir el primero de los símbolos de entrada

POSTULADO II. La información se codifica en cadenas de símbolos, y un autómata es un dispositivo que manipula cadenas de símbolos que se le presentan a su entrada, produciendo otras tiras o cadenas de símbolos a su salida.


a. OPCION B

b. OPCION D Incorrecto

c. OPCION A

d. OPCION C

DEFINICON DE ESTADO. Solo se deduce el Postulado I. El Postulado II hace referencia más a la definición de Autómata que ala de un estado.


DEFINICON DE ESTADO. Solo se deduce el Postulado I. El Postulado II hace referencia más a la definición de Autómata que ala de un estado.

8Puntos: 1

Teniendo en cuenta que podemos definir un Autómata como una máquina conceptual o teórica para el reconocimiento de patrones, entonces los siguientes componentes: Analizados Léxico, Analizador Sintáctico y Generador de Código corresponderían a una aplicación de un Autómata en el la implementación de:


a. Aplicaciones de Computador

b. Procesadores de texto Respuesta Incorrecta

c. Lenguajes de Programación

d. Compiladores


9Puntos: 1

Sea el vocabulario {1,2,3}, la expresión regular (1|2)* 3 indica el conjunto de todas las cadenas formadas con los símbolos 1,2 y 3 . Cuáles sentencias o cadenas son válidas :


a. 121211223 Correcto: Pueden formarse cadenas con los símbolos 1 y 2, sucedéndose cualquiér número de veces ( y en cualquiér órden) y siempre terminando la cadena en el símbolo 3

b. 221113 Correcto: Pueden formarse cadenas con los símbolos 1 y 2, sucedéndose cualquiér número de veces ( y en cualquiér órden) y siempre terminando la cadena en el símbolo 3

c. 2213311 Incorrecto: Pueden formarse cadenas con los símbolos 1 y 2, sucedéndose cualquiér número de veces ( y en cualquiér órden) y siempre terminando la cadena en el símbolo 3

d. 132211 Incorrecto: Pueden formarse cadenas con los símbolos 1 y 2, sucedéndose cualquiér número de veces ( y en cualquiér órden) y siempre terminando la cadena en el símbolo 3


Un posible alfabeto sería, digamos, {a, b}, y una cadena cualquiera sobre este alfabeto sería, por ejemplo, ababba. Un lenguaje sobre este alfabeto, que incluyera esta cadena, sería: el conjunto de todas las cadenas que contienen el mismo número de símbolos a que b.

10Puntos: 1

Los ítems que encontrará a continuación constan de una afirmación VERDADERA (tesis) y dos postulados también VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si los postulados se deducen lógicamente de la afirmación y seleccionar la respuesta en su hoja de cotejo, conforme a la siguiente instrucción:

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 sólo se deduce el postulado II.Marque D si ninguno de los postulados se deduce de la tesis.

TESIS. Los autómatas finitos determinísticos (AFD) son un subconjunto propio de los no determinísticos (AFN).

POSTULADO I. Todo AFD es un AFN

POSTULADO II. Se puede pensar entonces que los AFN son “más poderosos” que los AFD, en el sentido de que habría algunos lenguajes aceptados por algún AFN para los cuales no hay ningún AFD que los acepte


a. OPCION B Incorrecto

b. OPCION C

c. OPCION A

d. OPCION D

EQUIVALENCIA DE AUTÓMATAS FINITOS DETERMINISTICOS Y AUTÓMATAS FINITOS NO DETERMINÍSTICOS. Las equivalencias están en relación a la jerarquía de estos autómatas. Y en ambos postulados son coherentes.


EQUIVALENCIA DE AUTÓMATAS FINITOS DETERMINISTICOS Y AUTÓMATAS FINITOS NO DETERMINÍSTICOS. Las equivalencias están en relación a la jerarquía de estos autómatas. Y en ambos postulados son coherentes.

11Puntos: 1

Un Autómata Determinístico de estados finitos (DFA), M, es una quíntupla: (Q, Σ, qi , 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 función de transición de estados.

La condición de ser Determinístico es debido a que:


a. En cada instante lee un símbolo δ y dependiendo del símbolo y del estado s en el que se encuentra, cambia al estado dado por la función de transición: δ(s, σ)

Esto corresponde a la definición de Autómatas Determinísiticos (DFA). Estos autómatas se denominan determinísticos ya que en cada estado su comportamiento es fijo. Es decir, dado el estado y el símbolo en la cinta de entrada hay un único estado al cual puede pasar. . Todas los items son verdaderas.

b. El autómata comienza en el estado inicial y lee una secuencia de símbolos (símbolo por símbolo hasta que se acabe la secuencia).

Esto corresponde a la definición de Autómatas Determinísiticos (DFA). Estos autómatas se denominan determinísticos ya que en cada estado su comportamiento es fijo. Es decir, dado el estado y el símbolo en la cinta de entrada hay un único estado al cual puede pasar. . Todas los items son verdaderas.

c. Las transacciones están descritas por una función total.

d. Hay un único estado inicial. Correcto: Esto corresponde a la definición de Autómatas Determinísiticos (DFA). Estos autómatas se denominan determinísticos ya que en cada estado su comportamiento es fijo. Es decir, dado el estado y el símbolo en la cinta de entrada hay un único estado al cual puede pasar. . Todas los items son verdaderas.

Parcialmente correctoPuntos para este envío: 0.8/1.

El nombre “determinista” viene de la forma en que está definida la función de transición: si en un instante t la máquina está en el estado q y lee el símbolo a entonces, en el instante siguiente t + 1 la máquina cambia de estado y sabemos con seguridad cual es el estado al que cambia, que es precisamente δ(q, a).

12Puntos: 1

Los automatas se pueden representar mediante:


a. Tablas de transiciones

b. Diagrama de moore

c. El conjunto de tablas representativas

d. El conjunto de entradas de una maquina de turing


13Puntos: 1

Con referencia a los AFD, identifique cual característica no aplica a su descripción o funcionamiento.


a. Los automatas finitos tienen un numero finito de estados.

b. En un automata finito no determinista puede haber cero, una o mas transiciones desde un estado leyendo el mismo simbolo de entrada que conduzcan a estados diferentes (o posiblemente al mismo).

c. Para un automata finito no determinista siempre podran recorrerse una o mas rutas distintas al leer una cadena dada, y por tanto todas deberan examinarse para verificar si alguna termina en un estado de aceptacion.

d. En un automata finito determinista para cada estado existe exactamente una transicion por cada simbolo del alfabeto de la maquina.


14Puntos: 1

Cuál de las siguientes afirmaciones son verdaderas y aplican a su contexto o definición.


a. Los automatas finitos solo pueden aceptar lenguajes finitos.

b. Ninguna de las anteriores.

c. Las maquinas de turing y los automatas de pila son automatas finitos.

d. Los automatas finitos tienen un numero finito de estados.


15Puntos: 1

Un alfabeto es un conjunto finito de símbolos. De esta definición podemos afirmar correctamente: (Seleccione dos de las afirmaciones que sean correctas).


a. Por ser un alfabeto un conjunto finito de elementos, las posibles cadenas que se formen no pueden ser vacías

b. Dado un alfabeto, podemos formar palabras o cadenas con los símbolos del alfabeto

Correcto: Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está esta haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres

c. Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres.

Correcto: Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está esta haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres

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


En matemáticas, lógica, y las ciencias computacionales, un lenguaje formal es un conjunto de palabras (cadenas de caracteres) de longitud finita formadas a partir de un alfabeto (conjunto de caracteres) finito.

Documents

Act 5