Act 9: Quiz 2 - Unidad No. 2Revisin del intento 1Principio del formularioFinal del formularioComenzado eljueves, 24 de abril de 2014, 10:59

Completado eljueves, 24 de abril de 2014, 11:56

Tiempo empleado57 minutos 12 segundos

Puntos11/15

Calificacin22 de un mximo de 30 (73%)

Comentario -Correcto: Contest la totalidad de las preguntas.

Question 1 Puntos: 1 Considere la gramtica S Rc, R aRbR, R . Siendo w una cadena cualquiera generada por dicha gramtica, indique cul de las siguientes afirmaciones es falsa:Seleccione una respuesta. a. El nmero de letras a es mayor o igual al de letras b en todo prefijo de w. Prefijo de una cadena w es toda cadena no vaca x para la que existe una cadena u tal que w = xu.

b. El nmero de letras a es igual al de letras b en w

c. Las cadenas {abc, c} son aceptadas

d. w = xc | x (a b)* Esta afirmacin es falsa y es la respuesta correcta: Por ejemplo la cadena w = ac no es generada por la gramtica

CorrectoPuntos para este envo: 1/1.Question 2 Puntos: 1 Si una gramtica independiente del contexto tiene todas sus reglas de la forma: A wB, o bien de la forma A w, donde w es una cadena de uno o ms terminales, y A y Bson smbolos no terminales, entonces el lenguaje generado por dicha gramtica es: Seleccione una respuesta. a. Decidible

b. Regular Correcto

c. Estructurado por frases y no independiente del contexto

d. Independiente del contexto no regular

CorrectoPuntos para este envo: 1/1.Question 3 Puntos: 1 Indique cul de las siguientes afirmaciones es falsa:Seleccione una respuesta. a. La interseccin de dos lenguajes estructurados por frases es un lenguaje estructurado por frases

b. Todo lenguaje cuyo complementario sea un lenguaje finito es independiente del contexto

c. La unin de un nmero finito de lenguajes estructurados por frases es un lenguaje estructurado por frases

d. La interseccin de un lenguaje regular con un lenguaje independiente del contexto es siempre un lenguaje regular. Correcto: La interseccin del lenguaje regular xn ym y el lenguaje independiente del contexto xn yn es el lenguaje independiente del contexto no regular xn yn

CorrectoPuntos para este envo: 1/1.Question 4 Puntos: 1 Considere la gramtica G1 = {S aS/ aA/ a, A aB/ bS, B aB/ bB, C aA/ bC}y G2 = {S aS/ aA/ a, A bS}. Sean L1 y L2 los lenguajes generados respectivamente por G1 y G2; entonces: (Nota: el smbolo denota la relacin de inclusin estricta): Seleccione una respuesta. a. L1 = L2 Correcto: Las reglas que implican a los no terminales B y C no generan ninguna cadena.

b. L1 L2

c. L1 L2

d. L2 L1

CorrectoPuntos para este envo: 1/1.Question 5 Puntos: 1 Dada la ER (x*y)* aplique las propiedades de las ER y la jerarqua de los operadores y analice cul opcin es verdaderaSeleccione una respuesta. a. El lenguaje que representa la expresin regular (x*y)* Es el lenguaje formado por todas las cadenas terminadas en y ms la cadena vaca.

b. El lenguaje que representa la expresin regular (x*y)* es el formado por todas las cadenas que inician en xy con sucesiones repetidas de una o muchas veces. Esta apreciacin es falsa

c. El lenguaje que representa la expresin regular (x*y)* es el formado por todas las cadenas que inician en x.

d. El lenguaje que representa la expresin regular (x*y)* es el formado por todas las cadenas terminadas en y.

IncorrectoPuntos para este envo: 0/1.Question 6 Puntos: 1 Si a un Autmata se le adiciona un almacenamiento auxiliar, se est construyendo entonces:Seleccione una respuesta. a. Un Pushdown Automaton (PA)

b. Un Autmata No determinstico pero Finito

c. Un Autmata Determinstico Finito. Incorrecto

d. Una Turing Machine (TM)

Aadir al AF un almacenamiento auxiliar, que llamaremos pila, donde se podran ir depositando caracter por caracter cadenas arbitrariamente grandes, es el primer paso a la construccin de un AP a partir de un simple AF. IncorrectoPuntos para este envo: 0/1.Question 7 Puntos: 1 Sea M un autmata de pila. Indique cul de las siguientes afirmaciones es falsa:Seleccione una respuesta. a. Sea L={a, ab}. L puede ser aceptado por un autmata de pila determinista que siempre llegue a los estados de aceptacin con pila vaca

b. Si M es un autmata de pila determinista que siempre llega a los estados de aceptacin con pila vaca, entonces L(M) no puede ser aceptado por un autmata de pila no determinista

c. Sea L={a, ba}. L puede ser aceptado por un autmata de pila determinista que siempre llegue a los estados de aceptacin con pila vaca Esta afirmacin es verdadera ya que L es un lenguaje regular

d. Un autmata de Pila reconoce lenguajes que sean generados por gramticas de tipo2.

IncorrectoPuntos para este envo: 0/1.Question 8 Puntos: 1 Indique cul de las siguientes afirmaciones es verdaderaSeleccione una respuesta. a. Los autmatas de pila reconocen lenguajes generados por gramticas de tipo 3

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

c. Los autmatas finitos tienen un nmero finito de estados Correcto

d. Los autmatas finitos slo pueden aceptar lenguajes finitos

CorrectoPuntos para este envo: 1/1.Question 9 Puntos: 1 Cual de las siguientes afirmaciones es VERDADERASeleccione una respuesta. a. En un rbol de derivacin, una gramtica es ambigua, cuando hay dos o ms rboles de derivacin distintos para una misma cadena. Correcto. En este caso es ambigua por cuanto puede tener varias soluciones

b. Los lenguajes generados por una Gramtica Independiente del Contexto son llamados Lenguajes Regulares

c. En un rbol de derivacin cada nodo solamente puede tener otro hijo nodo. De lo contrario se formara otro nodo.

d. En los arboles de derivacin, los nodos races siempre derivan en dos ramas.

Es posible probar que cualquier palabra que sea aceptada por el AFD M, puede ser generada por la gramtica regular G. Esto significa que L(G) = L(M). CorrectoPuntos para este envo: 1/1.Question 10 Puntos: 1 Dado el siguiente rbol de derivacin, identifique las apreciaciones vlidas cuando se analiza su comportamiento y diseo:

Seleccione al menos una respuesta. a. El rbol representa una gramtica lineal por la izquierda, que genera el lenguaje L ={lambda, a,aa,aaa,}

b. La gramtica est representada como G = { S --->lambda | aS} Incorrecto: La gramtica en efecto puede generar tambin el lenguaje L ={lambda, a,aa,aaa,} , pero segn el rbol representado, es generado pro una gramtica lineal por la izquierda. Y esta opcin es una gramtica lineal por la derecha.

c. La gramtica est representada como: G = { S -lambda | Sa} y el lenguaje generado puede representarse con la expresin regular a*

d. El rbol representa las cadenas que inician en dos as seguida de una o ms as de un lenguaje regular Incorrecto: Pueden haber cadenas con una sola a

IncorrectoPuntos para este envo: 0/1.Question 11 Puntos: 1 Para simular el funcionamiento de un Autmata de Pila lo ms recomendable es hacer primero:Seleccione una respuesta. a. Simularlo en JFLAP con la cadena vaca Lambda para determinar si la pila inicia o no.

b. Simular su ejecucin en una MT que se comporta de igual forma

c. Simular su ejecucin, listando las situaciones sucesivas en que se encuentra, mediante una tabla llamada traza de ejecucin Correcto

d. Simular su ejecucin en un software (podra ser como Visual Autmata Simulator) iniciando con una cadena no vlida para determinar si el ciclo de la cinta inicia o no.

Para verificar el funcionamiento del autmata, podemos simular su ejecucin, listando las situaciones sucesivas en que se encuentra, mediante una tabla que llamaremos traza de ejecucin. Las columnas de una traza de ejecucin para un AP son: el estado en que se encuentra el autmata, lo que falta por leer de la palabra de entrada, y el contenido de la pila. CorrectoPuntos para este envo: 1/1.Question 12 Puntos: 1 Dada la gramtica S aS; S aSbS; S . Indique cul de las siguientes afirmaciones es falsa: Seleccione una respuesta. a. La cadena {b} es rechazada

b. Cualquier cadena generada por la gramtica contiene una subcadena no vaca donde el nmero de letras a es igual al nmero de letras b Esta es la opcin falsa. La cadena a que en efecto es aceptada , generada por la gramtica, no cumple esta condicin

c. El lenguaje generado por la gramtica es estructurado por frases

d. Para cualquier prefijo de una cadena generada por la gramtica se verifica que el nmero de letras a es mayor o igual al nmero de letras b. Prefijo de una cadena w es toda cadena no vaca x para la que existe una cadena u tal que w = xu

CorrectoPuntos para este envo: 1/1.Question 13 Puntos: 1 Se propone la siguiente GLC (Gramtica Libre de Contexto) para que genere el lenguaje de los palndromos en el alfabeto = {a,b}G =S aSa|bSb|a|b|Dada esa gramtica, determine cules reglas corresponden a los palndromos generados.Seleccione al menos una respuesta. a. S lambda ( Palndromos con smbolos pares ) Correcto: Al realizar el rbol de derivacin y el desarrollo de la gramtica, las reglas que llevan a crear palndromos impares son: S aproduce la cadena = baaab(impar)yS bproduce la cadena = babab(impar) y S lambda produce la cadena = baab(par).

b. S a (Palndromos con smbolos pares)

c. S b (Palndromos con smbolos pares)

d. S a | S b (Palndromos con smbolos impares) Correcto: Al realizar el rbol de derivacin y el desarrollo de la gramtica, las reglas que llevan a crear palndromos impares son: S aproduce la cadena = baaab(impar)yS bproduce la cadena = babab(impar) y S lambda produce la cadena = baab(par).

CorrectoPuntos para este envo: 1/1.Question 14 Puntos: 1 Que opciones son verdaderas alanalizar la siguiente gramtica.

Seleccione al menos una respuesta. a. Genera un lenguaje que acepta cadenas como: {aacab, aacbb, abcbb, bbbcaba} Correcto: El lenguaje corresponde a cadenas de forma wcv, donde w y v son cadenas de as y bs y w y v tienen la misma longitud pero v no es la cadena inversa de w

b. Genera el lenguaje que acepta cadenas como: {bacab, bbbc, aaac, aabcbb}

c. Las cadenas que puede aceptar corresponden a cadenas de forma wcv, donde w y v son cadenas de as bs y w y v tienen la misma longitud sin importar si v o wsoon inversas simultneamente.

d. Las cadenas que puede aceptar corresponden a cadenas de forma wcv, donde w y v son cadenas de as y bs y w y v tienen la misma longitud pero v no es la cadena inversa de w Correcto: cadenas como: {aacab, aacbb, abcbb, bbbcaba}

CorrectoPuntos para este envo: 1/1.Question 15 Puntos: 1 Cual de las siguientes afirmaciones se asocia correctamente al diseo y funcionamiento de los rboles de derivacin.Seleccione una respuesta. a. Los lenguajes generados por una Gramtica Independiente del Contexto son llamados Lenguajes Regulares

b. En un rbol de derivacin, una gramtica es ambigua cuando hay dos o ms rboles de derivacin distintos para una misma cadena. Respuesta Correcta: Una gramtica es ambiga cuando hay dos o ms rboles de derivacin distintos para una misma cadena

c. En un rbol de derivacin cada nodo solamente puede tener otro hijo nodo

d. En los rboles de derivacin, no es necesario usar nodo raz

Al derivar una cadena a travs de una GIC, el smbolo inicial se sustituye por alguna cadena. Los no terminales se van sustituyendo uno tras otro por otras cadenas hasta que ya no quedan smbolos no terminales, queda una cadena con slo smbolos terminales. A veces es til realizar un grfico de la derivacin. Tales grficos tienen forma de rbol y se llaman rbol de derivacin o rbol de anlisis. Para una derivacin dada, el smbolo inicial S etiqueta la raz del rbol. El nodo raz tiene unos nodos hijos para cada smbolo que aparezca en el lado derecho de la produccin, usados para reemplazar el smbolo inicial. De igual forma, cada smbolo no terminal tiene unos nodos hijos etiquetados con smbolos del lado derecho de la produccin usada para sustituir ese no terminal. CorrectoPuntos para este envo: 1/1.