1
Puntos: 1
Seleccione al menos
una respuesta.
a. Las operaciones: f(q,a,s)y f(q,e,s) con a ∑ ,, q Q y s (pertenecen) al alfabeto de la pila y no pueden estar simultáneamente
definidos o declarados.
b. La definición de la función de transición (f) requiere que haya por lo menos un símbolo en la pila. No se permiten operaciones
con la pila vacía.
c. El determinismo se da cuando no hay alternativas de movimiento para el mismo estado, usando la misma entrada y el mismo
símbolo de pila.
d. Las transiciones lambda en un AFPD permiten que el autómata cambie el contenido de la pila, sin procesar (o consumir)
símbolos sobre la cinta de entrada.
Identifique los aspectos que se deben tener para garantizar el determinismo en un Autómata de pila finito determinista (AFPD).
Tenga en cuenta además de los componentes (tupla) de la pila que::
f: es la función de transición:
e: es una transición dada espontanea.
Parcialmente correcto
Puntos para este envío: 0.5/1.
2
Puntos: 1
Seleccione al menos
una respuesta.
a. Los autómatas de pila aceptan exactamente los LLC. Por lo que: Si M es un AP, entonces L(M) es un LLC
b. Los AP son una extensión de los AF
c. Los AP son una extensión de los AF
d. Si se quiere meter cadenas a una pila, puede hacerse con una operación tipo “pop”
Los AP tienen ciertos comportamientos y asociaciones con los AF.
Seleccione las afirmaciones válidas:
Correcto
Puntos para este envío: 1/1.
3
Puntos: 1
Seleccione al menos
una respuesta.
a. S → lambda ( Palíndromos con símbolos pares )
b. S → b (Palíndromos con símbolos pares)
c. S → a (Palíndromos con símbolos pares)
d. S → a | S → b (Palíndromos con símbolos impares)
Se propone la siguiente GLC (Gramática Libre de Contexto) para que genere el lenguaje de lospalíndromos en el alfabeto ∑ = {a,b}
G = S → aSa | bSb | a | b | lambda
Dada esa gramática, determine cuáles reglas corresponden a los palíndromos generados.
Act 8: Lección Evaluativa Unidad No. 2
Revisión del intento 1
Comenzado el jueves, 17 de abril de 2014, 21:33
Completado el jueves, 17 de abril de 2014, 22:25
Tiempo empleado 52 minutos 41 segundos
Puntos 8.5/10
Calificación 25.5 de un máximo de 30 (85%)
Comentario - Correcto
AUTOMATAS Y LENGUAJES FORMALES Perfil Salir
Campus13 2014-1 http://66.165.175.211/campus13_20141/mod/quiz/review.php?q=468&a...
1 de 4 19/04/2014 05:14 p.m.
Al realizar el árbol de derivación y el desarrollo de la gramática, las reglas que llevan a crear palíndromosimpares son: S → a produce la cadena ω = baaab (impar) y S → b produce la cadena ω = babab (impar) yS → alanda produce la cadena ω = baab (par).
Correcto
Puntos para este envío: 1/1.
4
Puntos: 1
Seleccione al menos
una respuesta.
a. La derivación de la cadena {abaca} es: S --> SbS --> SbScS ---> SbSca ---> Sbaca ---> abaca
b. La derivación de la cadena {abaca} es: S ---> ScS ---> SbScS ---> abScS ---> abacS ---> abaca
c. La gramática que lo genera es: S --> SbS | ScS | a
d. La gramática que lo genera es: S -->SaS | SbS | Sc | a
Para eL siguiente árbol de derivación identifique las operaciones correctas sobre el mismo:
Correcto
Puntos para este envío: 1/1.
5
Puntos: 1
Seleccione al menos
una respuesta.
a. Con un autómata de pila no puede reconocerse un lenguaje regular
b. Cuando se dice que un AFPD (autómata de pila determinista) es más sencillo , se refiere a que es menos potente y no se
refiere ala sencillez de su diseño.
c. Para reconocer un lenguaje regular mediante un autómata de pila no es necesario que el alfabeto de la pila contenga ningún
símbolo
d. Para reconocer un lenguaje regular mediante un autómata de pila el alfabeto de la pila debe contener al menos un símbolo
Indique cuál de las siguientes afirmaciones es verdadera:
Parcialmente correcto
Puntos para este envío: 0.5/1.
6
Puntos: 1
Seleccione una
respuesta.
a. Formas de Greibach
b. Formas de LIC
c. Formas canónicas que restrinjan los tipos de producciones que pueden utilizarse.
d. Producciones de tipo GIC con un solo nodo terminal
Cuando las gramáticas son demasiado extensas y generan árboles de derivación grandes, se suele usar:
La definición de una gramática independiente del contexto es demasiado amplia, y por lo tanto, es deseableestablecer una forma canónica que restrinja los tipos de producciones que pueden utilizarse.
Correcto
Puntos para este envío: 1/1.
7
Puntos: 1
Seleccione una
respuesta.
a. Al igual que los AF, los AP tienen estados finales, que permiten distinguir cuando una palabra de entrada es aceptada
Acerca del funcionamiento de un Autómata de Pila, cuál de las siguientes operaciones o comportamientosNO las hace este autómata.
Campus13 2014-1 http://66.165.175.211/campus13_20141/mod/quiz/review.php?q=468&a...
2 de 4 19/04/2014 05:14 p.m.
Para verificar el funcionamiento del autómata, podemos simular su ejecución, listando las situacionessucesivas en que se encuentra, mediante una tabla que llamaremos “traza de ejecución”. Las columnas deuna traza de ejecución para un AP son: el estado en que se encuentra el autómata, lo que falta por leer dela palabra de entrada, y el contenido de la pila
Correcto
Puntos para este envío: 1/1.
8
Puntos: 1
Seleccione al menos
una respuesta.
a. ∑+ = Conjunto de todas las cadenas positivas excepto la vacía
b. ∑0 = {lambda} Conjunto cuyo único elemento es la palabra vacía.
c. ∑ * = Conjunto de todas las cadenas de cualquier longitud sobre ∑
d. ∑0 = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
Si ∑ es un alfabeto, se le llama ∑n al conjunto de todas las palabras de longitud n sobre ∑.
Identifique las notaciones de conjuntos válidas para la creación de palabras sobre el alfabeto ∑
La longitud de una cadena ω que se denota como |ω| es el número de letras que aparecen en ω. A lacadena que no tiene símbolos o que es lo mismo decir que tiene longitud cero, se le llama palabra vacía. Si∑ es un alfabeto, se le llama ∑ n al conjunto de todas las palabras de longitud n sobre ∑. La estrella *genera el conjunto de todas las cadena de cualquier longitud sobre ∑. Si se analiza ∑ + esta representa alconjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.
Parcialmente correcto
Puntos para este envío: 0.5/1.
9
Puntos: 1
Seleccione una
respuesta.
a. El conjunto de cadenas que pueda generar la ER = a*b*a
b. {baaaa, aaaaa, bba}
c. {aa, aaaa, bbba, ba, bba, baaa, baba}
d. {a,b}
Dada la siguiente gramática regular G , identifique el conjunto de cadenas o palabras válidas que puede generar el Autómata Finito que lo
representa: (Para el desarrollo del ejercicio se sugiere graficar o recrear el autómata)
S → aA | bA
A → aB | bB | a
B → aA | bA
Correcto
Puntos para este envío: 1/1.
10
Puntos: 1
Seleccione al menos
una respuesta.
a. La representación de las derivaciones de la gramática siempre se hacen de forma vertical. Nunca de forma comprimida u
horizontal
b. Un árbol ordenado y etiquetado D es un árbol de derivación para una gramática libre de contexto G(A)
c. El lenguaje definido por una gramática G, denotado L(G) es el conjunto de cadenas de símbolos terminales, que se pueden
derivar partiendo del axioma de la gramática, y empleando para las derivaciones las reglas de producción de P
d. La longitud de las cadenas de derivaciones nunca puede ser nula y siempre se grafican en el Arbol de derivación iniciando
por la Izquierda La representación de las derivaciones de la gramática siempre se hacen de forma vertical. Nunca de forma
comprimida u horizontal
De entre las cuatro clases de gramáticas de la clasificación de Chomsky, el grupo más importante, desde elpunto de vista de la aplicabilidad en teoría de compiladores, es el de las gramáticas independientes o libresdel contexto. Las gramáticas de este tipo se pueden usar para expresar la mayoría de estructurassintácticas de un lenguaje de programación.
Aspectos que caracterizan este tipo de gramáticas son:
Una gramática es un conjunto de reglas para formar correctamente las frases de un lenguaje; así tenemosla gramática del español, del francés, etc. La formalización que presentaremos de la noción de gramática esdebida a N. Chomsky, y está basada en las llamadas reglas gramaticales.
Correcto
Puntos para este envío: 1/1.
Campus13 2014-1 http://66.165.175.211/campus13_20141/mod/quiz/review.php?q=468&a...
3 de 4 19/04/2014 05:14 p.m.
Usted se ha autentificado como ANGY ELISSET MUÑOZ (Salir)
301405A
Campus13 2014-1 http://66.165.175.211/campus13_20141/mod/quiz/review.php?q=468&a...
4 de 4 19/04/2014 05:14 p.m.
Top Related