Download Act 9 Quiz 2.docx PDF

TitleAct 9 Quiz 2.docx
TagsLinguistics Psychology & Cognitive Science Cognitive Science Theoretical Computer Science Formalism (Deductive)
File Size408.8 KB
Total Pages8
Document Text Contents
Page 1

Act 9: Quiz 2 - Unidad No. 2

Revisión del intento 1

Comenzado el jueves, 24 de abril de 2014, 10:59

Completado el jueves, 24 de abril de 2014, 11:56

Tiempo empleado 57 minutos 12 segundos

Puntos 11/15

Calificación 22 de un máximo de 30 (73%)

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

Question 1

Puntos: 1

Considere la gramática S →Rc, R → aRbR, R → λ. Siendo w una cadena cualquiera

generada por dicha gramática, indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.



a. El número 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 vacía x para la que

existe una cadena u tal que w = xu.





b. El número 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 afirmación es falsa y es la

respuesta correcta: Por ejemplo la

cadena w = ac no es generada por

la gramática

Correcto

Puntos para este envío: 1/1.

Question 2

Puntos: 1

Si una gramática 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 más terminales, y A y

Bson símbolos no terminales, entonces el lenguaje generado por dicha gramática es:

Seleccione una respuesta.



a. Decidible




b. Regular Correcto



c. Estructurado por frases y no independiente del contexto




d. Independiente del contexto no regular


Correcto

Puntos para este envío: 1/1.

Question 3

Puntos: 1

Page 3

formado por todas las cadenas terminadas en y.

Incorrecto

Puntos para este envío: 0/1.

Question 6

Puntos: 1

Si a un Autómata se le adiciona un almacenamiento auxiliar, se está construyendo

entonces:

Seleccione una respuesta.



a. Un Pushdown Automaton (PA)




b. Un Autómata No determinístico pero Finito




c. Un Autómata Determinístico Finito. Incorrecto



d. Una Turing Machine (TM)


Añadir al AF un almacenamiento auxiliar, que llamaremos pila, donde se podrían ir

depositando caracter por caracter cadenas arbitrariamente grandes, es el primer paso a la

construcción de un AP a partir de un simple AF.

Incorrecto

Puntos para este envío: 0/1.

Question 7

Puntos: 1

Sea M un autómata de pila. Indique cuál de las siguientes afirmaciones es falsa:

Seleccione una respuesta.



a. Sea L={a, ab}. L puede ser aceptado por un autómata

de pila determinista que siempre llegue a los estados de

aceptación con pila vacía




b. Si M es un autómata de pila determinista que siempre

llega a los estados de aceptación con pila vacía, entonces

L(M) no puede ser aceptado por un autómata de pila no

determinista





c. Sea L={a, ba}. L puede ser aceptado por un autómata

de pila determinista que siempre llegue a los estados de

aceptación con pila vacía

Esta afirmación es

verdadera ya que L es

un lenguaje regular



d. Un autómata de Pila reconoce lenguajes que sean

generados por gramáticas de tipo2.

Incorrecto

Puntos para este envío: 0/1.

Question 8

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera

Seleccione una respuesta.



a. Los autómatas de pila reconocen lenguajes generados por gramáticas de

tipo 3



b. Las máquinas de Turing y los autómatas de pila son autómatas finitos





c. Los autómatas finitos tienen un número finito de estados Correcto



d. Los autómatas finitos sólo pueden aceptar lenguajes finitos

Page 5

={lambda, a,aa,aaa,…}



b. La gramática está representada

como G = { S --->lambda | aS}



Incorrecto: La gramática en efecto puede generar

también el lenguaje L ={lambda, a,aa,aaa,…} ,

pero según el árbol representado, es generado pro

una gramática lineal por la izquierda. Y esta

opción es una gramática lineal por la derecha.



c. La gramática está representada

como: G = { S -lambda | Sa} y

el lenguaje generado puede

representarse con la expresión

regular a*





d. El árbol representa las cadenas

que inician en dos a”s seguida de

una o más a”s de un lenguaje

regular

Incorrecto: Pueden haber cadenas con una sola

“a”

Incorrecto

Puntos para este envío: 0/1.

Question 11

Puntos: 1

Para simular el funcionamiento de un Autómata de Pila lo más recomendable es hacer

primero:

Seleccione una respuesta.



a. Simularlo en JFLAP con la cadena vacía Lambda para determinar si la

pila inicia o no.



b. Simular su ejecución en una MT que se comporta de igual forma




c. Simular su ejecución, listando las situaciones sucesivas en que se

encuentra, mediante una tabla llamada “traza de ejecución
Correcto



d. Simular su ejecución en un software (podría ser como Visual Autómata

Simulator) iniciando con una cadena no válida para determinar si el ciclo

de la cinta inicia o no.


Para verificar el funcionamiento del autómata, podemos simular su ejecución, listando

las situaciones sucesivas en que se encuentra, mediante una tabla que llamaremos “traza

de ejecución”. Las columnas de una traza de ejecución para un AP son: el estado en que

se encuentra el autómata, lo que falta por leer de la palabra de entrada, y el contenido de

la pila.

Correcto

Puntos para este envío: 1/1.

Question 12

Puntos: 1

Dada la gramática S → aS; S→ aSbS; S→ λ. Indique cuál de las siguientes

afirmaciones es falsa:

Seleccione una respuesta.



a. La cadena {b} es rechazada




b. Cualquier cadena generada por la gramática

contiene una subcadena no vacía donde el número de

Esta es la opción falsa. La

cadena a que en efecto es

Page 6

letras a es igual al número de letras b aceptada , generada por la

gramática, no cumple esta

condición



c. El lenguaje generado por la gramática es

estructurado por frases



d. Para cualquier prefijo de una cadena generada por

la gramática se verifica que el número de letras a es

mayor o igual al número de letras b. Prefijo de una

cadena w es toda cadena no vacía x para la que existe

una cadena u tal que w = xu



Correcto

Puntos para este envío: 1/1.

Question 13

Puntos: 1

Se propone la siguiente GLC (Gramática Libre de Contexto) para que genere el lenguaje

de los palíndromos en el alfabeto ∑ = {a,b}

G = S → aSa | bSb | a | b | 

Dada esa gramática, determine cuáles reglas corresponden a los palíndromos generados.

Seleccione al menos una respuesta.



a. S → lambda (

Palíndromos con

símbolos pares )

Correcto: Al realizar el árbol de derivación y el desarrollo de

la gramática, las reglas que llevan a crear palíndromos

impares son: S → a produce la cadena ω = baaab (impar) y S

→ b produce la cadena ω = babab (impar) y S → lambda

produce la cadena ω = baab (par).



b. S → a

(Palíndromos con

símbolos pares)




c. S → b

(Palíndromos con

símbolos pares)




d. S → a | S → b

(Palíndromos con

símbolos impares)



Correcto: Al realizar el árbol de derivación y el desarrollo de

la gramática, las reglas que llevan a crear palíndromos

impares son: S → a produce la cadena ω = baaab (impar) y S

→ b produce la cadena ω = babab (impar) y S → lambda

produce la cadena ω = baab (par).

Correcto

Puntos para este envío: 1/1.

Question 14

Puntos: 1

Page 7

Que opciones son verdaderas al analizar la siguiente gramática.


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 a’s y b’s 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 a’s ó b’s y w y v tienen

la misma longitud sin importar si v o wsoon

inversas simultáneamente.





d. Las cadenas que puede aceptar

corresponden a cadenas de forma wcv, donde

w y v son cadenas de a’s y b’s y w y v tienen

la misma longitud pero v no es la cadena

inversa de w

Correcto: cadenas como: {aacab,

aacbb, abcbb, bbbcaba}

Correcto

Puntos para este envío: 1/1.

Question 15

Puntos: 1

Cual de las siguientes afirmaciones se asocia correctamente al diseño y funcionamiento

de los árboles de derivación.

Seleccione una respuesta.



a. Los lenguajes generados por una

Gramática Independiente del Contexto son

llamados Lenguajes Regulares




b. En un árbol de derivación, una gramática

es ambigua cuando hay dos o más árboles

de derivación distintos para una misma

cadena.

Respuesta Correcta: Una gramática es

“ambigüa” cuando hay dos o más

árboles de derivación distintos para

una misma cadena

Similer Documents