Act 5 Automatas Y Lenguajes Formales

Act 5: Quiz 1 - Unidad No. 1

Revisión del intento 1

Comenzado el viernes, 27 de septiembre de 2013, 13:55

Completado el viernes, 27 de septiembre de 2013, 14:53

Tiempo empleado 57 minutos 59 segundos

Puntos 13.25/15

Calificación 22.1 de un máximo de 25 (88%)

Comentario - Correcto: Contestó la totalidad de las preguntas.

Question1

Puntos: 1

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

Seleccione una respuesta.

a. Uno

b. Dos

c. No hay numero minimo

d. Depende del alfabeto sobre el que esta definido.

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

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

Seleccione una respuesta.

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

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. Los automatas finitos tienen un numero finito de estados.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Uno de los principales factores determinantes en la revolución en el ámbito de la ciencia, la técnica y la cultura de nuestros días es el desarrollo de la Informática PORQUE Un lenguaje natural como el inglés o el español son la clase de lenguajes que han evoucionado con el paso del tiempo y tienen por fin la comunicación humana.

Seleccione una respuesta.

a. La Afirmación es VERDADERA, pero la Razón es una proposición FALSA

b. La Afirmación y la Razón son VERDADERAS y la Razón es una explicación CORRECTA de la Afirmación

c. La Afirmación y la Razón son VERDADERAS pero la Razón NO es una explicación CORRECTA de la Afirmación Respuesta Correcta

d. La Afirmación es FALSA, pero la Razón es una proposición VERDADERA

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 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 finito

b. Una máquina de Turing.

c. Un autómata de pila determinista Correcto

d. Un autómata de pila no determinista

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

La definición formal de un Lenguaje Regular (ele) L, se da solo si cumple ciertas condiciones. Siendo ∑ un alfabeto, el conjunto de los lenguajes regulares sobre ∑ = {a,b} puede estar formado por:

Selecione al menos una respuesta.

Seleccione al menos una respuesta.

a. {ab} es regular pues resulta de la concatenación de {a} y {b} Correcto

b. {a,b} es regular pues resulta de la unión de {a} y {b} Correcto

c. vacío y {lambda } son lenguajes regulares Correcto

d. {a} y {b} son lenguajes regulares Correcto

Definición formal de Lenguaje Regular. Por la definición anterior, el conjunto de los lenguajes regulares formado por el lenguaje vacío, los lenguajes unitarios incluido lambda y todos los lenguajes obtenidos a partir de la unión, concatenación y cerradura o estrella de Kleene.

Definición formal de Lenguaje Regular. Por la definición anterior, el conjunto de los lenguajes regulares formado por el lenguaje vacío, los lenguajes unitarios incluido lambda y todos los lenguajes obtenidos a partir de la unión, concatenación y cerradura o estrella de Kleene.. Todas los items son verdaderas

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

3. Partiendo de la definición de que un Autómata Finito Determinístico (AFD) está dado por la quíntupla: A = (Q, ∑, f, q0 , F) donde:

• Q es un conjunto de estados.

• ∑ es el alfabeto de entrada

• f: Q X ∑ → Q es la función (total) de transición.

• q0 que pertenece a Q es el estado inicial.

Y que para el ejercicio, el autómata acepta las cadenas (01) n 1) :

,

A = ({q0 , q1 , q2 , q3 } , {0,1} , f , q0 , { q2 })

Representado mediante el grafo:

Seleccione una respuesta.

a. TABLA D ETRANSICION A

b. TABLA DE TRANSICION C

c. TABLA DE TRANSICION D

d. TABLA DE TRANSICION B Correcto: La transición correcta es la B. está identificado de forma correcta el estado inicial, el estado final con un * y las transiciones (con los elementos de entrada) acordes al grafo. Opción B.

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

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

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

Seleccione una respuesta.

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

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 tiene un solo estado Inicial que se puede representar por un * o por un círculo doble.

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 almacenamiento de información adicional) Correcto. Los estados son definidos desde el inicio y son finitos.

Al describir una máquina de estados finitos en particular, debemos incluir las informaciones que varían de un autómata

...