quiz 1 automatas y lenguajes formales
Post on 26-Oct-2015
208 Views
Preview:
TRANSCRIPT
10/10/13 Campus13 2013-2
66.165.175.211/campus13_20132/mod/quiz/review.php?q=11528&attempt=113079 1/6
1
Puntos: 1
Seleccione una
respuesta.
a. Un automata reconoce una cadena cuando alcanza un estado de aceptacion durante su lectura
b. Un automata f inito determinista utilizado como reconocedor de lenguajes con al menos una cadena necesariamente tiene que
tener al menos un estado de aceptacion.
c. Dada una gramatica regular G, siempre existe un automata f inito M tal que L(G) = L(M) y M tiene un unico estado de aceptacion.
d. Un automata f inito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la coleccion de cadenas de dicho
lenguaje.
Una de las siguientes afirmaciones NO aplica a los lenguajes que reconocen un autómata. Identifíquela
Correcto
Puntos para este envío: 1/1.
2
Puntos: 1
Seleccione una
respuesta.
a. Expresión regular (bb|ab)*
b. Expresión regular (ac|b|b)*
c. Expresión regular (q|q )*
d. Expresión regular (ac|b)* Correcto: Se está representando una operación de una Epresión Regular (El cierre u operaciòn
estrella).
Acorde al siguiente diagrama de Moore. Identifique que expresión representa:
La operación de conjuntos de unión posibilita tener lenguajes de varios elementos y si se añade la operación * cerradura o estrella de
Kleene que se deriva naturalmente de la concatenación, tambien es factible producir lenguajes infinitos.
Correcto
Puntos para este envío: 1/1.
Act 5: Quiz 1 - Unidad No. 1
Revisión del intento 1
Finalizar revisión
Comenzado el jueves, 5 de septiembre de 2013, 21:55
Completado el jueves, 5 de septiembre de 2013, 22:46
Tiempo empleado 50 minutos 56 segundos
Puntos 13.75/15
Calificación 22.9 de un máximo de 25 (92%)
Comentario - Correcto: Contestó la totalidad de las preguntas.
AUTOMATAS Y LENGUAJES FORMALES Perfil Salir
Campus13 2013-II ► 301405A ► Cuestionarios ► Act 5: Quiz 1 - Unidad No. 1 ► Revisión del intento 1
10/10/13 Campus13 2013-2
66.165.175.211/campus13_20132/mod/quiz/review.php?q=11528&attempt=113079 2/6
3
Puntos: 1
Seleccione al menos
una respuesta.
a. vacío y {lambda } son lenguajes regulares Correcto
b. {a,b} es regular pues resulta de la unión de {a} y {b}
c. {a} y {b} son lenguajes regulares Correcto
d. {ab} es regular pues resulta de la concatenación de {a} y {b} Correcto
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.
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
Parcialmente correcto
Puntos para este envío: 0.8/1.
4
Puntos: 1
Seleccione una
respuesta.
a. OPCION D
b. OPCION C
c. OPCION A
d. OPCION B Correcto
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.
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.
Correcto
Puntos para este envío: 1/1.
5
Puntos: 1
Seleccione una
respuesta.
a. En un automata f inito determinista para cada estado existe exactamente una transicion por cada simbolo del alfabeto de la
maquina.
b. Para un automata f inito no determinista siempre podran recorrerse una o mas rutas distintas al leer una cadena dada, y por
tanto todas deberan examinarse para verif icar si alguna termina en un estado de aceptacion.
c. En un automata f inito 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).
d. Los automatas f initos tienen un numero f inito de estados.
Con referencia a los AFD, identifique cual característica no aplica a su descripción o funcionamiento.
Correcto
Puntos para este envío: 1/1.
10/10/13 Campus13 2013-2
66.165.175.211/campus13_20132/mod/quiz/review.php?q=11528&attempt=113079 3/6
6
Puntos: 1
Seleccione al menos
una respuesta.
a. Las cadenas válidas para ese alfabeto obedece a
sus seis posibles combinaciones: {0, 1, 01, 10, 00, 11}
b. Pueden ser cadenas válidas como: {lambda, 0, 1. 00,
11, 010, 0110, 000000, 101101, 10001}
Correcto: Este lenguaje {0,1} tiene cadenas infinitas (muchisimas se
pueden combinar como palindromos que se lean iagual al derecho y al
reves).
c. Este Lenguaje tiene cadenas f initas
d. Este Lenguaje tiene cadenas infinitas Correcto: Este lenguaje {0,1} tiene cadenas infinitas (muchisimas se
pueden combinar como palindromos que se lean iagual al derecho y al
reves).
Un ejemplo de “Lenguaje” es el conjunto de “palíndromos” (cadenas que se leen igual hacia adelante, que hacia atrás). Para el caso del
alfabeto { 0, 1} Es válido afirmar: (Seleccione dos respuestas).
Tenga en cuenta que el símbolo lambda (usado en autómatas), http://es.wikipedia.org/wiki/Lambda
Los lenguajes regulares se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes, como por
ejemplo en el lenguaje L1 siguiente: L1 = {ab, abab, ababab, abababab, . . .} En este ejemplo se aprecia que las palabras de L1 son
simplemente repeticiones de “ab” cualquier número de veces. Aquí la “regularidad” consiste en que las palabras contienen “ab” algún
número de veces.
Correcto
Puntos para este envío: 1/1.
7
Puntos: 1
Seleccione una
respuesta.
a. Lenguaje regular
b. Lenguaje estructurado por frases (en sentido estricto)
c. Es una maquina de turing.
d. Lenguaje independiente del contexto (en sentido estricto)
Los palindromos (palabras capicuas) del idioma castellano, tales como "a", "y", "dad", "oso", "erre", etc., constituyen un:
Correcto
Puntos para este envío: 1/1.
8
Puntos: 1
Seleccione al menos
una respuesta.
a. El conjunto de entradas de una maquina de turing
b. El conjunto de tablas representativas
c. Diagrama de moore
d. Tablas de transiciones
Los automatas se pueden representar mediante:
Correcto
Puntos para este envío: 1/1.
9
Puntos: 1
Seleccione una
respuesta.
a. Los automatas f initos tienen un numero f inito de estados.
b. Los automatas f initos solo pueden aceptar lenguajes f initos.
c. Las maquinas de turing y los automatas de pila son automatas f initos.
d. Ninguna de las anteriores.
Cuál de las siguientes afirmaciones son verdaderas y aplican a su contexto o definición.
Correcto
Puntos para este envío: 1/1.
10
Puntos: 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.
10/10/13 Campus13 2013-2
66.165.175.211/campus13_20132/mod/quiz/review.php?q=11528&attempt=113079 4/6
Seleccione una
respuesta.
a. OPCION B
b. OPCION C
c. OPCION A Correcto
d. OPCION D
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
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.
Correcto
Puntos para este envío: 1/1.
11
Puntos: 1
Seleccione una
respuesta.
a. Un automata f inito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la coleccion de cadenas de dicho
lenguaje.
b. Un automata f inito determinista M reconoce un lenguaje L(M) si la coleccion de cadenas de dicho lenguaje es determinista.
c. Ninguna de las afirmaciones anteriores es cierta.
d. Un automata f inito determinista M reconoce un lenguaje L(M) si acepta todas las cadenas de dicho lenguaje.
Indique cual de las siguientes afirmaciones es la que corresponde cuando se trata de los lenguajes que puede reconoce un AF.
Correcto
Puntos para este envío: 1/1.
12
Puntos: 1
Seleccione al menos
una respuesta.
a. Las cadenas que se forman a partir de un alfabeto f inito, resultan ser inf initas.
b. Por ser un alfabeto un conjunto f inito de elementos, las posibles cadenas que se formen no pueden ser vacías
c. Dado un alfabeto, podemos formar palabras o cadenas con los símbolos del alfabeto
d. Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres.
Un alfabeto es un conjunto finito de símbolos. De esta definición podemos afirmar correctamente: (Seleccione dos de las afirmaciones que
sean correctas).
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.
Incorrecto
Puntos para este envío: 0/1.
13
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:
10/10/13 Campus13 2013-2
66.165.175.211/campus13_20132/mod/quiz/review.php?q=11528&attempt=113079 5/6
Seleccione una
respuesta.
a. TABLA DE
TRANSICION B
Correcto: La transición correcta es la B. está identif icado de forma correcta el estado inicial, el estado f inal con
un * y las transiciones (con los elementos de entrada) acordes al grafo. Opción B.
b. TABLA DE
TRANSICION C
c. TABLA D
ETRANSICION A
d. TABLA DE
TRANSICION D
La tabla de transición correspondiente es:
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.
14
Puntos: 1
Seleccione una
respuesta.
a. La Afirmación y la Razón son VERDADERAS y la Razón es una explicación CORRECTA de la Afirmación
b. La Afirmación es VERDADERA, pero la Razón es una proposición FALSA
c. La Afirmación es FALSA, pero la Razón es una proposición VERDADERA
d. 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
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.
10/10/13 Campus13 2013-2
66.165.175.211/campus13_20132/mod/quiz/review.php?q=11528&attempt=113079 6/6
Correcto
Puntos para este envío: 1/1.
15
Puntos: 1
Gramáticas
de tipo 0
Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing
Gramáticas
de tipo 3
Gramáticas regulares. Generan los lenguajes regulares
Gramáticas
de tipo 1
Gramáticas sensibles al contexto. Generan los lenguajes sensibles al contexto
Gramáticas
de tipo 2
Gramáticas libres del contexto. Generan los lenguajes independientes del contexto
Como especificar la sintaxis de un lenguaje?: Se utiliza la jerarquía de Chomsky; la jerarquía de Chomsky es una clasificación jerárquica
de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956. Acorde
a esto, asocie correctamente esta clasificación.
Como especificar la sintaxis de un lenguaje?: Se utiliza la jerarquía de Chomsky; la jerarquía de Chomsky es una clasificación jerárquica
de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.
Correcto
Puntos para este envío: 1/1.
Finalizar revisión
Usted se ha autentificado como Ricardo A ndres Mejia (Salir)
301405A
top related