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
Indique cuál
de las siguientes afirmaciones es falsa:
Seleccione
una respuesta.
|
|
a. La
intersección 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
unión de un número finito de lenguajes estructurados por frases es un
lenguaje estructurado por frases
|
|
|
|
d. La
intersección de un lenguaje regular con un lenguaje independiente del
contexto es siempre un lenguaje regular.
|
Correcto:
La intersección del lenguaje regular xn ym y el
lenguaje independiente del contexto xn yn es el
lenguaje independiente del contexto no regular xn yn
|
Correcto
Puntos para
este envío: 1/1.
Question 4
Puntos: 1
Considere la gramática 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 símbolo
⊂ denota la relación de inclusión 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
|
Correcto
Puntos para
este envío: 1/1.
Question 5
Puntos: 1
Dada la ER
(x*y)* aplique las propiedades de las ER y la jerarquía de los operadores y
analice cuál opción es verdadera
Seleccione
una respuesta.
|
|
a. El
lenguaje que representa la expresión regular (x*y)* Es el lenguaje formado
por todas las cadenas terminadas en y más la cadena vacía.
 |
|
|
|
b. El
lenguaje que representa la expresión regular (x*y)* es el formado por todas
las cadenas que inician en xy con sucesiones repetidas de una o muchas veces.
 |
Esta
apreciación es falsa
|
|
|
c. El
lenguaje que representa la expresión regular (x*y)* es el formado por todas
las cadenas que inician en x.
|
|
|
|
d. El
lenguaje que representa la expresión regular (x*y)* es el 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
|
Correcto
Puntos para
este envío: 1/1.
Question 9
Puntos: 1
Cual de las
siguientes afirmaciones es VERDADERA
Seleccione
una respuesta.
|
|
a. 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.
|
Correcto.
En este caso es ambigua por cuanto puede tener varias soluciones
|
|
|
b. Los
lenguajes generados por una Gramática Independiente del Contexto son llamados
Lenguajes Regulares
|
|
|
|
c. En un
árbol de derivación cada nodo solamente puede tener otro hijo nodo. De lo
contrario se formaría otro nodo.
|
|
|
|
d. En los
arboles de derivación, los nodos raíces siempre derivan en dos ramas.
|
Es posible
probar que cualquier palabra que sea aceptada por el AFD M, puede ser generada
por la gramática regular G. Esto significa que L(G) = L(M).
Correcto
Puntos para
este envío: 1/1.
Question 10
Puntos: 1
Dado el
siguiente árbol de derivación, identifique las apreciaciones válidas cuando se analiza
su comportamiento y diseño:
Seleccione
al menos una respuesta.
|
|
a. El
árbol representa una gramática lineal por la izquierda, que genera el
lenguaje L ={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 letras a es igual al número de letras b
|
Esta es la
opción falsa. La cadena a que en efecto es 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 | lambda
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
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
|
|
|
c. En un
árbol de derivación cada nodo solamente puede tener otro hijo nodo
|
|
|
|
d. En los
árboles de derivación, no es necesario usar nodo raíz
|
Al derivar
una cadena a través de una GIC, el símbolo inicial se sustituye por alguna
cadena. Los no terminales se van sustituyendo uno tras otro por otras cadenas
hasta que ya no quedan símbolos no terminales, queda una cadena con sólo
símbolos terminales. A veces es útil realizar un gráfico de la derivación.
Tales gráficos tienen forma de árbol y se llaman “árbol de derivación” o “árbol
de análisis”. Para una derivación dada, el símbolo inicial “S” etiqueta la raíz
del árbol. El nodo raíz tiene unos nodos hijos para cada símbolo que aparezca
en el lado derecho de la producción, usados para reemplazar el símbolo inicial.
De igual forma, cada símbolo no terminal tiene unos nodos hijos etiquetados con
símbolos del lado derecho de la producción usada para sustituir ese no
terminal.
Correcto
Puntos para
este envío: 1/1.
