automatas corregidas unidad 1 y 2

1

Puntos: 1

Que significan las reglas de la forma A → lambda

Seleccione al menos una respuesta.

	a. Se le llaman producciones nulas	Correcto: Producciones Nulas: Son de la forma A → lambda
	b. Que estén en una gramática, deben permitir que el lenguaje no se cambie o altere
	c. No se pueden eliminar en una gramática ya que si se hiciere, modifican el lenguaje
	d. Generan lenguajes que contienen la palabra vacía

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question2

Puntos: 1

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

Seleccione al menos una respuesta.

	a. Genera el lenguaje que acepta cadenas como: {bacab, bbbc, aaac, aabcbb}
	b. 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.
	c. 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
	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

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question3

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
	b. L1 = L2
	c. L2 ⊂ L1	Incorrecto
	d. L1 ≠ L2

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

Respecto a la definición de Ambigüedad, cuáles afirmaciones aplican al concepto y lo clarifican en el tema de automatización cuando intervienen gramáticas de diferente tipo: (seleccione más de una opción).

Seleccione al menos una respuesta.

	a. Un lenguaje es inherentemente ambiguo si no existe una gramática que la describe y que no sea ambigua
	b. Sea una gramática G. Una sentencia x que pertenece a L(G) es ambigua si puede obtenerse por medio de varias derivaciones distintas correspondientes a árboles de derivación diferentes.
	c. Se presenta cuando cada instrucción tiene una sola interpretación en cada rama de un árbol de derivación y tiene un fin de parada en el segundo nodo.	Incorrecto. La ambigüedad es una propiedad indeseada en los lenguajes de programación. Cada instrucción debe tener solo una interpretación.
	d. Una gramática es ambigua si genera alguna sentencia ambigua

La ambigüedad es una propiedad indeseada en los lenguajes de programación. Cada instrucción debe tener solo una interpretación.

Incorrecto

Puntos para este envío: 0/1.

Question5

Puntos: 1

Una gramática independiente del contexto (GIC) genera un lenguaje independiente del contexto (LIC), lo que indica que hay LIC que no son lenguajes regulares y por lo tanto:

Seleccione una respuesta.

	a. El conjunto de los LIC contiene al conjunto de los lenguajes regulares.
	b. El conjunto de los lenguajes regulares contiene al conjunto de los LIC.
	c. El conjunto de los lenguajes regulares y el conjunto de los LIC son conjuntos independientes.	Incorrecto: Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC).
	d. El conjunto de los lenguajes regulares contiene al conjunto de las GIC.

Una gramática independiente del contexto (GIC) es una cuádrupla G=(N, Σ, S, P), donde: N: es una colección finita (no vacía) de símbolos no terminales. Σ: es un alfabeto. S: es un no terminal llamado símbolo inicial. P: un conjunto de producciones tal que P⊆ N (N∪ Σ)*. Los lenguajes generados por una GIC son llamados Lenguajes Independientes del Contexto (LIC)

Incorrecto

Puntos para este envío: 0/1.

Question6

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. La gramática está representada como: G = { S -lambda | Sa} y el lenguaje generado puede representarse con la expresión regular a*
	b. El árbol representa una gramática lineal por la izquierda, que genera el lenguaje L ={lambda, a,aa,aaa,…}
	c. 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”
	d. La gramática está representada como G = { S --->lambda | aS}

Incorrecto

Puntos para este envío: 0/1.

Question7

Puntos: 1

Indique cuál de las siguientes afirmaciones es verdadera

Seleccione una respuesta.

	a. Los autómatas finitos tienen un número finito de estados
	b. Los autómatas finitos sólo pueden aceptar lenguajes finitos	Incorrecto
	c. Las máquinas de Turing y los autómatas de pila son autómatas finitos
	d. Los autómatas de pila reconocen lenguajes generados por gramáticas de tipo 3

Incorrecto

Puntos para este envío: 0/1.

Question8

Puntos: 1

La combinación de autómatas se demostró en los Autómatas Finitos de la Unidad 1 en as que era viable combinar dos Autómatas que generaban el miso lenguaje y obtener otro que genera las mismas cadenas que los autómatas combinados.
Con referencia a los Autómatas de Pila (AP), este tema de combinación tiene aspectos a analizar. identifique cuál es válido para estas operaciones:

Seleccione una respuesta.

	a. Solo la operación de Unión de los lenguajes de dos AP es permitida.
	b. Se pueden obtener AP que acepten operaciones de Unión y Concatenación de los lenguajes aceptados por los Autónomas de Pila dados.
	c. Las operaciones de combinar AP solo es viable cuando los dos Autónomas leen el mismo alfabeto.	Incorrecto
	d. Un AP se puede combinar con una MT siempre y cuando lean y acepten el mismo lenguaje.

En los AP también es posible aplicar métodos de combinación modular de autómatas, como se hizo con los autómatas finitos. En particular, es posible obtener AP que acepten la unión y concatenación de los lenguajes aceptados por dos AP dados.

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

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

Seleccione una respuesta.

	a. 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.
	b. Simular su ejecución, listando las situaciones sucesivas en que se encuentra, mediante una tabla llamada “traza de ejecución	Correcto
	c. Simularlo en JFLAP con la cadena vacía Lambda para determinar si la pila inicia o no.
	d. Simular su ejecución en una MT que se comporta de igual forma

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.

Question10

Puntos: 1

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

Seleccione una respuesta.

	a. Una Turing Machine (TM)
	b. Un Pushdown Automaton (PA)
	c. Un Autómata Determinístico Finito.
	d. Un Autómata No determinístico pero Finito

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.

Question11

Puntos: 1

Que apreciaciones son ciertas con referencia a lo que describe el siguiente árbol de derivación:

Seleccione al menos una respuesta.

	a. La ER que representa el lenguaje que acepta ese árbol de derivación es ab*c
	b. Acepta el lenguaje de las palabras que empiezan por S y terminan en una o muchas A”s. La ER que lo representa es SA*
	c. Acepta el lenguaje de las palabras que empiezan por “a”, terinan por “c” y además en medio de estas dos letras pueden haber una “b” o muchas “b”s	Correcto
	d. Este árbol de derivación es producto de la gramática lineal por la derecha: S –>aA | A ---> bA | c

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question12

Puntos: 1

La relación entre un AP y un LLC (Lenguaje Libre de contexto) permite que dada una Gramática G, existe entonces un AP que acepta exactamente el lenguaje generado por G.

Dado el siguiente autómata de pila (AP) cuyo funcionamiento se representa en la siguiente tabla, identifique la gramática correcta y sus reglas que aceptan el LLC dado por el AP.

Seleccione una respuesta.

	a. S –> 0A0 | 1S2 | 10
	b. S –> 0A0 | 1S0 | 2 | 0
	c. S –> 0A0 | 1S1 | 2
	d. S –> 0A0 | 1S2 | 1 | 0	Incorrecto: En la pila lo que falta por leer viene siendo la cadena que se evalúa .Esta gramática no es la que recorre el árbol que permite esa salida.

Incorrecto

Puntos para este envío: 0/1.

Question13

Puntos: 1

Considere la gramática: S→ 0S, S→ 1S, S→ S0, S→ λ. Indique cuáles de las

siguientes afirmaciones son verdaderas

Seleccione al menos una respuesta.

	a. Existen derivaciones distintas que generan cadenas idénticas
	b. Las cadenas {0101, 1001] no son parte del lenguaje que genera
	c. La regla S→ S0 es innecesaria	Correcto
	d. La gramática es equivalente a S→0S, S→ 1S, S→ λ

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question14

Puntos: 1

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

Seleccione una respuesta.

	a. El lenguaje generado por la gramática es estructurado por frases
	b. La cadena {b} es rechazada
	c. 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	Esta afirmación es correcta: ejemplo la cadena {aabbb} no es aceptada
	d. 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

Incorrecto

Puntos para este envío: 0/1.

Question15

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, 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
	b. Un autómata de Pila reconoce lenguajes que sean generados por gramáticas de tipo2.
	c. 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
	d. 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

Incorrecto

Puntos para este envío: 0/1.

1

Puntos: 1

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 ∑

Seleccione al menos una respuesta.

	a. ∑ * = Conjunto de todas las cadenas de cualquier longitud sobre ∑
	b. ∑0 = Conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.	Incorrecto
	c. ∑0 = {lambda} Conjunto cuyo único elemento es la palabra vacía.
	d. ∑+ = Conjunto de todas las cadenas positivas excepto la vacía

La longitud de una cadena ω que se denota como |ω| es el número de letras que aparecen en ω. A la cadena 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 al conjunto de todas las cadenas sobre el alfabeto ∑ excepto la vacía.

Incorrecto

Puntos para este envío: 0/1.

Question2

Puntos: 1

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

Seleccione una respuesta.

	a. El conjunto de cadenas que pueda generar la ER = a*b*a	Incorrecto: Las cadenas no son aceptadas cuando se recorre la gramática.
	b. {a,b}
	c. {baaaa, aaaaa, bba}
	d. {aa, aaaa, bbba, ba, bba, baaa, baba}

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

Los AP tienen ciertos comportamientos y asociaciones con los AF.

Seleccione las afirmaciones válidas:

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. Si se quiere meter cadenas a una pila, puede hacerse con una operación tipo “pop”
	c. Los AP son una extensión de los AF	Correcto
	d. Los AP son una extensión de los AF

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question4

Puntos: 1

Respecto a la relación entre un AF y un AP cuál afirmación es cierta:

Seleccione una respuesta.

	a. Un AP es infinito por su capacidad de memoria. Un AF es finito por su número de estados.
	b. Los AF y los AP tienen la misma capacidad de memoria	Incorrecto: los AP tienen mayor capacidad de memoria
	c. Todo lenguaje aceptado por un AF es también aceptado por un AP
	d. Las gramáticas que generan los lenguajes que pueden representar estos autómatas o máquinas, son las GLC

En los AP también es posible aplicar métodos de combinación modular de autómatas, como se hizo con los autómatas finitos. En particular, es posible obtener AP que acepten la unión y concatenación de los lenguajes aceptados por dos AP dados.

Incorrecto

Puntos para este envío: 0/1.

Question5

Puntos: 1

Dado el siguiente autómata finito (AF), reconoce el lenguaje generado por la gramática:

Seleccione una respuesta.

	a. G={S ---> 0A| lambda,, A ---> 0A | 1B, B ---> 1B|lambda}
	b. G = { S --->B |lambda , A ---> 1B | lambda,, B ---> lambda}
	c. G= {S -->0B | 0A , A ---> 1B | lambda , B ---> lambda	Incorrecto
	d. G = { S --->A |lambda , A ---> 0B | lambda,, B ---> lambda}

Incorrecto

Puntos para este envío: 0/1.

Question6

Puntos: 1

Del diseño y naturaleza de los autómatas de pila (PDA), es válido afirmar:

Seleccione una respuesta.

	a. Para poder simular un autómata de Pila se debe tener en cuenta: Las columnas de una traza de ejecución para un AP son: el estado en que se encuentra el autómata, lo que ha leido hasta el momento o estado actual al inicio de la simulación, y el contenido de la memoria al final del recorrido.
	b. Un Autómata de Pila al igual que una Máquina de Turing o un Autómata Finito, su definición básica es de naturaleza no determinista
	c. Un autómata de pila no puede hacer las funciones de "contador" ya que sus recorridos varían en la cinta y lo que le importa a esta automatización es el estado final y la salida del dato.	Incorrecto: Los autómatas de Pila se usan como contadores de datos, es una aplicación más de estas máquinas. De hecho este conteo es usado para comparar otros elementos de entrada y comportamientos.
	d. A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que recuerda cada cual

A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a que recuerda cada cual.

Incorrecto

Puntos para este envío: 0/1.

Question7

Puntos: 1

Dado un alfabeto ∑, los símbolos Ø, lambda, y los operadores + (unión), ∙ (concatenación) y * (clausura), se define una EXPRESION REGULAR (ER) sobre el alfabeto ∑ en la que son válidas las siguientes relaciones:

Nota. ω es una cadena sobre un lenguaje L

Seleccione al menos una respuesta.

	a. Si ω = lambda entonces L (lambda) = { lambda}
	b. Si ω = a y a pertenece ∑ entonces L (ω) no pertenece ∑
	c. Si ω = Ø entonces L (ω) = Ø
	d. Si ω* es una ER entonces L (ω*) no es una ER

La notación de conjuntos nos permite describir los lenguajes regulares, pero nosotros quisiéramos una notación en que las representaciones de los lenguajes fueran simplemente texto (cadenas de caracteres). Así las representaciones de los lenguajes regulares serían simplemente palabras de un lenguaje (el de las representaciones correctamente formadas).

Incorrecto

Puntos para este envío: 0/1.

Question8

Puntos: 1

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.

Seleccione al menos una respuesta.

	a. 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.	Correcto
	b. 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.
	c. 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.
	d. 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.

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question9

Puntos: 1

De entre las cuatro clases de gramáticas de la clasificación de Chomsky, el grupo más importante, desde el punto de vista de la aplicabilidad en teoría de compiladores, es el de las gramáticas independientes o libres del contexto. Las gramáticas de este tipo se pueden usar para expresar la mayoría de estructuras sintácticas de un lenguaje de programación.

Aspectos que caracterizan este tipo de gramáticas son:

Seleccione al menos una respuesta.

	a. 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
	b. Un árbol ordenado y etiquetado D es un árbol de derivación para una gramática libre de contexto G(A)
	c. La representación de las derivaciones de la gramática siempre se hacen de forma vertical. Nunca de forma comprimida u horizontal	Incorrecto
	d. 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

Una gramática es un conjunto de reglas para formar correctamente las frases de un lenguaje; así tenemos la gramática del español, del francés, etc. La formalización que presentaremos de la noción de gramática es debida a N. Chomsky, y está basada en las llamadas reglas gramaticales.

Incorrecto

Puntos para este envío: 0/1.

Question10

Puntos: 1

Para que una palabra de entrada sea aceptada en un AP se deben cumplir las condiciones siguientes:

Seleccione al menos una respuesta.

	a. La pila debe tener lambda como elemento final.
	b. La palabra de entrada se debe haber agotado (consumido totalmente).
	c. El AP se debe encontrar en un estado final.	Correcto: para que una palabra de entrada sea aceptada en un AP se deben cumplir todas las condiciones siguientes: 1. La palabra de entrada se debe haber agotado (consumido totalmente). 2. El AP se debe encontrar en un estado final. 3. La pila debe estar vacía.
	d. La pila debe estar vacía.

A la hora de diseñar un AP tenemos que repartir lo que requiere ser “recordado” entre los estados y la pila. Distintos diseños para un mismo problema pueden tomar decisiones diferentes en cuanto a qué recuerda cada cual.

Parcialmente correcto

Puntos para este envío: 0.3/1.

1

Puntos: 1

Dada la siguiente gramática: 

S → xS / S → yA / S → zB / A → yA / A → yB / B → zB / B → Lambda 

Compuesta por los estados S, A, B y en la que los tres son estados finales o de aceptación, analice cual afirmación es verdadera:

Seleccione una respuesta.

	a. La gramática no genera ningún lenguaje porque presenta más de un estado de aceptación o final.	Incorrecto: la gramática si genera un lenguaje y no genera la cadena vacía.
	b. La gramática no genera la cadena vacía
	c. La gramática solo genera cadenas de un símbolo y la cadena vacía
	d. La gramática genera la cadena vacía

Incorrecto

Puntos para este envío: 0/1.

Question2

Puntos: 1

Dado el alfabeto ∑= {a,b}, identifique cuál afirmación es falsa.

Seleccione una respuesta.

	a. La expresión regular b*ab* (ab*ab*)* representa al lenguaje de las cadenas con un número impar de letras a
	b. La expresión regular b*(ab*ab*)* representa al lenguaje de las cadenas con un número par de letras a	Esto es afirmativo
	c. La expresión regular (b*ab*ab*a) * representa al lenguaje de las cadenas con un número múltiplo de 3 de letras “a”
	d. La expresión regular b*a*b* representa al lenguaje de las cadenas que pueden o no tener “a”

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

Dada la Gramática S→aS; S→aSbS; S→lambda .

Indique cuáles de las siguientes afirmaciones no corresponden al desarrollo de la misma o al tipo de cadenas o palabras ω que pueda generar.

Seleccione al menos una respuesta.

	a. Las cadenas ω que acepta la gramática siempre van a empezar por a. Además el lenguaje generado por la gramática es estructurado por frases
	b. Las cadenas que acepta la gramática siempre van a empezar por b. Además el lenguaje generado por la gramática es “no es estructurado por frases”.	Incorrecto
	c. Cualquier cadena ω generada por la gramática contiene una subcadena no vacía donde algunas veces el número de letras a es igual al número de letras b.
	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 ω es toda cadena no vacía x para la que existe una cadena u tal que ω=xu

Las gramáticas cuyas reglas son de la forma A ---> aB o bien A ---> a, donde A y B son variables, y a es un caracter terminal. A estas gramáticas se les llama regulares.

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

Cuando se diseñan AP o se formalizan, se utilizan notaciones gráficas parecidas a la de los diagramas de los AF. Con respecto a esto: ¿qué aspectos de diseños son válidos para formalizar un AP.?

Seleccione al menos una respuesta.

	a. Si se da la transición “a/x/c” indica que se saca de la pila un carácter “a”, luego se avanza una posición “x” en la pila, y se mete “c” a la pila.
	b. Para que una palabra de entrada sea aceptada en un AP debe cumplir tres condiciones. Una de ellas es que el AP se debe encontrar en un estado final.	Correcto: El funcionamiento de un AP indica una sintaxis en la que el caractér del centro o símbolo hace referencia a lo que se saca o no de la pila. Otra condición para que la cadena sea aceptada en un AP es que la pila esté vacía,
	c. Si se da la transición “a/x/c” indica que se consume de la entrada un carácter “a”, se avanza una posición “x” y se mete “c” a la pila.
	d. Si se da la transición “a/x/c” indica que se consume de la entrada un carácter “a”, no se saca nada de la pila, y se mete “c” a la pila.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question5

Puntos: 1

Un árbol de derivación, para una derivación dada se construye: (seleccione que las operaciones que son necesarias): Teniendo en cuenta el siguiente árbol.

Seleccione al menos una respuesta.

	a. Todos los nodos hoja están etiquetados con símbolos terminales.
	b. El nodo raíz tiene unos hijos para cada símbolo que aparece en el lado derecho de la producción usada para reemplazar el símbolo inicial.
	c. Creando un nodo raíz que se etiqueta con el símbolo inicial.	Correcto
	d. Los nodos que no tienen hijos, deben ser etiquetados con símbolos terminales.

Parcialmente correcto

Puntos para este envío: 0.3/1.

Question6

Puntos: 1

Para u AP, la función de transición también se puede representar mediante un diagrama donde los nodos representan los estados y los arcos transiciones, Dada la siguiente transición como se muestra en la figura, identifique las acciones correctas que haría el movimiento de la pila.

Seleccione una respuesta.

	a. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es X que se va a sustituir por lambda al cambiar al nuevo estado q1 y avanzar la cabeza lectora.
	b. El estado actual es q0. La cabeza lectora apunta al tope X que es donde inicia la lectura del símbolo “a” que entra al pasar al estado q1 y sustituir lambda por X.	Incorrecto
	c. El estado actual es q0. La cabeza lectora apunta al símbolo “a”. El tope de la pila es “a” como primer símbolo a leer que se va a sustituir por lambda al cambiar al nuevo estado q1 y avanzar la cabeza lectora.
	d. El estado actual es q0. La cabeza lectora apunta al símbolo “lambda”. El recorrido de la pila es de izquierda a derecha. El tope de la pila es X que no se modifica al cambiar al nuevo estado q1 y avanzar la cabeza lectora.

Incorrecto

Puntos para este envío: 0/1.

1

Puntos: 1

Acerca del comportamiento de los estados en un autómata, indique que apreciaciones son válidas con respecto a su función y comportamiento:

Seleccione al menos una respuesta.

	a. Se define como 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.	Correcto
	b. Un estado de un autómata funciona de tal forma que cuando reciba a su entrada una determinada cadena de símbolos, indica si dicha cadena pertenece o no al lenguaje
	c. Un estado de aceptación también puede ser inicial. Solo para autómatas finitos no
	d. 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.	Correcto

Correcto

Puntos para este envío: 1/1.

Question2

Puntos: 1

Cuáles afirmaciones son válidas y que surgen de un análisis de las ER (Expresiones Regulares):

Analice los autómatas dados:

Seleccione al menos una respuesta.

	a. La ER (0+1)*01 genera cadenas válidas para el autómata “A”, pero no para las del autómata “B”.
	b. La ER (0+1)*11(01)* genera cadenas válidas para el autómata “B” pero no para las del autómata “A”.
	c. La ER (1*00*1(00*1)*1)*1*00*1(00*1)* genera las mismas cadenas para el Autómata “A” el autómata “B”.	Correcto: Ambas ER son equivalentes y aplican para el autómata. Se debe aplicar la propiedad de la operación matemática de la estrella de Kleene.
	d. La ER (0+1)*01 genera las mismas cadenas para el Autómata “B” y del autómata “A”	Correcto: Ambas ER son equivalentes y aplican para el autómata. Se debe aplicar la propiedad de la operación matemática de la estrella de Kleene.

Correcto

Puntos para este envío: 1/1.

Question3

Puntos: 1

Sean dos lenguajes L1 y L2 definidos sbre el mismo alfabeto ∑, la operación que se representa a continuación es:

L = L1L2 = {xy / x pertenece L1 Ʌ y pertenece L2}

Seleccione una respuesta.

	a. Unión de lenguajes
	b. Asociación de lenguajes
	c. Operación cerrada de dos lenguajes
	d. Concatenación de lenguajes	Correcto: La concatenación de ambos lenguajes estará formada por todas las palabras obtenidas al concatenar una palabra cualquiera de L1 con otra de L2.

Correcto

Puntos para este envío: 1/1.

Question4

Puntos: 1

Se pueden generar palíndromos (cadenas ω) sobre el alfabeto ∑ = {0,1}. Evidentemente este lenguaje tiene infinitas cadenas

Selecciones las afirmaciones válidas con referencia al anterior postulado.

Seleccione al menos una respuesta.

	a. Los símbolos de un alfabeto, definen el tipo de lenguaje a que pertenece.
	b. Existe un lenguaje denominado el lenguaje vacío que es un conjunto vacío y se denota por {Ø}. El lenguaje vacío no debe confundirse con un lenguaje que contenga una sola cadena.	Correcto
	c. ω = lambda ó cadena vacía y ω = 0 ; Son palíndromos
	d. Los palíndromos son una excepción de los lenguajes regulares y no hacen parte de la jerarquía de Chomsky	Incorrecto: Los palíndromos tienen regularidades. Son lenguajes de tipo 3

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question5

Puntos: 1

Sea el autómata A = (∑, Q, f, q1, F) donde:

∑ ={a,b}, Q = {q1, q2, q3, q4}, F= { q4} y la función f vienen dada por la siguiente tabla:

Determine qué aspectos son válidos para el autómata

Seleccione al menos una respuesta.

	a. Es un Autómata Finito Determinístico (AFD)
	b. Es un Autómata Finito Determinístico con lambda transiciones
	c. El lenguaje reconocido por el autómata es: a (b*b | a*b) a*	Correcto: Es un AFND. El lenguaje que reconoce es : a (b*b | a*b) a* o también a (b* | a* ) ba* para efectos de mejor comprensión, hay que recrear o realizar el autómata mediante un diagrama de Moore
	d. El lenguaje reconocido por el autómata es: a (b* | a* ) ba*	Correcto: Es un AFND. El lenguaje que reconoce es : a (b*b | a*b) a* o también a (b* | a* ) ba* para efectos de mejor comprensión, hay que recrear o realizar el autómata mediante un diagrama de Moore

Correcto

Puntos para este envío: 1/1.

Question6

Puntos: 1

Dadas las siguientes gramáticas, asócielas a los enunciados que se presentan de forma correcta. Tenga en cuenta que como Símbolo inicial se toma a “S” que son los estados iniciales y como símbolos no terminales los estados en el orden de su nombramiento. El conjunto finito de símbolos terminales son los símbolos del alfabeto ∑ del autómata.

Seleccione al menos una respuesta.

	a. La Gramática D corresponde a una representación válida del lenguaje que acepta el Autómata “C”.
	b. La Gramática B corresponde a una representación válida del lenguaje que acepta el Autómata ”D”.	Incorrecto. La gramática no le corresponde a los autómatas dados
	c. La Gramática C corresponde a una representación válida del lenguaje que acepta el Autómata con lambda transiciones del Autómata “E”	Correcto: La gramática C es la de un AFND con landa transiciones.
	d. La Gramática A corresponde a una representación válida del lenguaje que acepta los Autómatas “A” y “B”.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question7

Puntos: 1

Dada la siguiente gramática con las siguientes producciones,

S --> ab

S ---> aSb

que derivaciones son válidas al usar sus reglas:

Seleccione al menos una respuesta.

	a. aabb	Correcto
	b. ab
	c. Ba
	d. Bbaa

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question8

Puntos: 1

Dado el siguiente autómata: Cambie los símbolos del alfabeto asociando a = 0 y b =1 . Para las siguientes opciones,(que están en base 10 o decimal), conviértalas a base 2 (binario) y recorra el autómata e identifique cuál número acepta el autómata.

Seleccione una respuesta.

	a. 182
	b. 205
	c. 73	Incorrecto: equivale a la cadena 01001001 y esta no es reconocida
	d. 253

Incorrecto

Puntos para este envío: 0/1.

Question9

Puntos: 1

Las siguientes cadenas:

{Lambda,aaa, bb, bbb, aabb, aba, abaaa, abbaa}

son generadas expresadas por la ER

Seleccione una respuesta.

	a. ( a | b)*
	b. (a + b ) *
	c. (a.b)*
	d. (a,b)*	Incorrecto

Incorrecto

Puntos para este envío: 0/1.

Question10

Puntos: 1

Expresiones regulares: Determine que igualdades son válidas:

Seleccione al menos una respuesta.

	a. aa+b*a = (aa+b*)a	Incorrecto
	b. a+a=a
	c. a(aa+b)* + a(aa+b)* = a(aa+b)*	Correcto
	d. a*=a*.a*=(a*)*	Correcto: Por asociación

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question11

Puntos: 1

Dados los siguientes autómatas determine que características aplican en cuanto a su comportamiento y diseño.

Seleccione al menos una respuesta.

	a. La cadena bababbaabb la reconocen los dos autómatas.	Correcto: esta cadena es aceptada por ambos autómatas. Además amas máquinas son equivalentes
	b. El autómata A es “equivalente” al autómata B	Correcto: aceptan el mismo lenguaje.
	c. El autómata A es un AFND y reconoce el mismo lenguaje que el autómata B	Correcto. Además el autómata B resúltate de un proceso de equivalencia es un AFD.
	d. El autómata A NO es “equivalente” al autómata B.

Correcto

Puntos para este envío: 1/1.

Question12

Puntos: 1

Dado el siguiente autómata, analice si es posible su minimización y seleccione las opciones válidas para su análisis:

Seleccione al menos una respuesta.

	a. Los estados q2 y q3 son equivalentes. Dado que transitan igual para los dos símbolos del alfabeto. Por tanto se pueden fusionar en no solo.
	b. El autómata no se puede minimizar. No hay estados equivalentes y los estados distinguibles no se pueden modificar.	Incorrecto. El autómata se puede minimizar y os estados equivalentes o candidatos a comparar son q2 y q3.
	c. Si es posible minimizarlos y el autómata resultante tendrá tres estados	Correcto
	d. El estado final q1 es equivalente con el inicial. (teorema de equivalencia de estados). Por tanto el autómata es candidato a minimizarse.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question13

Puntos: 1

Dentro de la jerarquía y clasificación de los lenguajes (Chomsky) identifique que asociaciones están erradas.

Seleccione al menos una respuesta.

	a. Los lenguajes que no poseen restricciones o de tipo 0, son reconocidos mediante Autómatas Finitos No Deterministas (AFND)
	b. Una gramática regular o de tipo 3, puede generar Autómatas finitos (AF)	Correcto: esta afirmación es errada ya que las gramáticas generan lenguajes. Las máquinas o autómatas reconocen es lenguajes.
	c. Los lenguajes regulares pueden ser pueden ser descritos mediante expresiones regulares (ER)	Esta afirmación es verdadera. Un lenguaje puede ser descrito mediante una expresión regular (expresar de forma compacta cómo son todas las cadenas de símbolos que le pertenecen).
	d. Los lenguajes libres de contexto o de tipo 2, pueden ser generados por los autómatas de pila (AP)	Correcto: esta afirmación es errada ya que un lenguaje es descrito por una máquina y no generado por la máquina.

Parcialmente correcto

Puntos para este envío: 0.7/1.

Question14

Puntos: 1

Dados los siguientes dos autómatas finitos, identifique los aspectos válidos en cuanto a su comportamiento.

Seleccione una respuesta.

	a. Los autómatas reconocen cadenas o palabras diferentes.
	b. La cadena {bb} solo es reconocida por un autómata.
	c. Corresponde a un proceso de conversión o transformación de un AFND a un AFD. Ambos autómatas reconocen el mismo lenguaje	Correcto: El primer autómata es un AFND y el segundo es el resultado de un proceso de conversión a AFD
	d. Los dos autómatas son producto de una gramática libre de contexto GLC

Correcto

Puntos para este envío: 1/1.

Question15

Puntos: 1

Acerca de la clasificación de los lenguajes, identifique las afirmaciones válidas con referencia a la jerarquía y comportamiento de los mismos:

Seleccione al menos una respuesta.

	a. Al clasificar lenguajes, no se están clasificando máquinas que los reconozcan, Se clasifican gramáticas que los generan.
	b. Según la clasificación de lenguajes definida por Chomsky y que la llamó “jerarquía de lenguajes”, los “Lenguajes Regulares” es la clase más pequeña en la jerarquía, e incluye a los lenguajes más simples. Estos se llaman así porque sus palabras contienen “regularidades” o repeticiones de los mismos componentes.	Correcto
	c. Los lenguajes son en sí conjuntos de secuencias de símbolos y las clases de lenguajes son conjuntos de conjuntos de secuencias de símbolos.	Correcto
	d. Se llama “clase de lenguajes” a conjuntos de lenguajes que comparten cierta propiedad dada.	Correcto

Correcto

Puntos para este envío: 1/1.

1

Puntos: 1

Algunas operaciones y propiedades sobre lenguajes y ER que se pueden realizar son:

Seleccione al menos una respuesta.

	a. El orden de prioridad de los operadores es, de mayor a menor: *, ∙, + Este orden puede alterarse mediante paréntesis, de forma análoga a como se hace con las expresiones aritméticas.	Correcto
	b. (B U C) ∙ A = (B ∙ A) U (C ∙ A)
	c. La concatenación de lenguajes sobre un alfabeto es una operación cerrada, y tiene un elemento neutro que es el lenguaje {lambda}.	Correcto. Es parte de las propiedades de los lenguajes
	d. A ∙ (B U C) = (A ∙ B) U (A ∙ C)

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question2

Puntos: 1

Sea el Autómata Finito (AF) A= (∑, Q, f. q1, F) donde ∑ = {0,1} , Q = {q1, q2, q3, q4}, F= { q2}  y definimos la función de transición fpor la tabla siguiente:

Indique cuál es lenguaje generado por el autómata:

Seleccione una respuesta.

	a. 1*(1)
	b. 1(01) *
	c. 0(010)*	Incorrecto: Las cadenas inician con 1. Por consiguiente la ER no es válida.
	d. 1( 1) (0)*

Incorrecto

Puntos para este envío: 0/1.

Question3

Puntos: 1

Dado el siguiente Autómata Finito (AF).

La Expresión Regular (ER) que denota el Lenguaje que representa es.

Seleccione una respuesta.

	a. xx*zx((zx+x*z)x)*
	b. xz(xz)*((x*+xx*z)x)*	Incorrecto: La ER no expresa as cadenas válidas que acepta el autómata.
	c. xxzx((zx)*z)*
	d. xx*zx((z+xx*z)x)*

Incorrecto

Puntos para este envío: 0/1.

Question4

Puntos: 1

Que representa la siguiente figura:

Seleccione una respuesta.

	a. Que representa la siguiente figura:
	b. Un Autómata que acepta palabras o cadenas que contienen únicamente b´s o a´s
	c. Un Autómata de tipo AFND válido.	Correcto: Es un Autómata Finito No Determinístico (AFND) válido. Es una extensión válida de un AFD. Permite que de cada nodo del diagrama de estados salga un número de flechas mayor o menor que |∑|
	d. No representa un autómata válido por que el mismo estado inicial es el mismo estado final.

Correcto

Puntos para este envío: 1/1.

Question5

Puntos: 1

Dado los siguientes dos autómatas A y B, analice los enunciados dados e identifique cuales son verdaderos.

Seleccione al menos una respuesta.

	a. Solo el Autómata A reconoce la cadena vacía lambda
	b. El Autómata A es un AFND y el Autómata B es un AFD
	c. El Autómata B tiene un error de diseño. Un AF no puede tener dos estados de aceptación	Incorrecto
	d. Los dos Autómatas reconocen el mismo Lenguaje.	Correcto: Ambos autómatas reconocen el mismo lenguaje,

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question6

Puntos: 1

Dado los autómatas M1 y M2 siguientes, cuáles relaciones entre estas dos máquinas son válidas.

Seleccione al menos una respuesta.

	a. Los Autómatas M1 y M2 aceptan ambos el lenguaje a *	Correcto: La equivalencia se da por la aceptación de lenguajes. Ambos aceptan el lenguaje a * y aceptan exactamente el mismo lenguaje
	b. Los Autómatas M1 y M2 no son equivalentes porque ambos rechazan el lenguaje b*. La equivalencia se da en la aceptación de lenguajes.
	c. Los Autómatas M 1 y M2 son equivalentes: M1 ≈ M2 , por que aceptan exactamente el mismo lenguaje	Correcto: La equivalencia se da por la aceptación de lenguajes. Ambos aceptan el lenguaje a * y aceptan exactamente el mismo lenguaje
	d. Los Autómatas M1 y M2 son iguales pero no equivalentes

Correcto

Puntos para este envío: 1/1.

Question7

Puntos: 1

Para el siguiente Autómata Finito denotado como: A2= (E. Q, f, q1, F) donde E = {0,1}, F = {q2} y Q = {q1, q2, q3, q4}, identifique correctamente el Lenguaje que genera y la expresión regular:

Seleccione una respuesta.

	a. L = (A2 ) = {0, 001, 00100, …} = { 1(01)n |n ≠ 0} La expresión regular es: 0(01) *
	b. L = (A2 ) = {0, 001, 01111, …} = { 1(10)n |n ≤ 0} La expresión regular es: 0(01) *
	c. L = (A2 ) = {0, 111, 11100, …} = { 1(10)n |n = 0} La expresión regular es: 1(01)+
	d. L = (A 2) = {1, 101, 10101, …} = { 1(01)n |n ≥ 0} La expresión regular es: 1(01) *	Correcto: El lenguaje generado se obtiene partiendo del estado inicial y recorriendo todos los caminos posibles para alcanzar el estado final

Correcto

Puntos para este envío: 1/1.

Question8

Puntos: 1

Si se considera un autómata finito M con transiciones lambda que reconoce el lenguaje L: De la relación entre determinista y no determinista de los autómatas, y el comportamiento de las cadenas vacías (lambda), es válido afirmar

Seleccione al menos una respuesta.

	a. Las transiciones lambda solo son aceptadas en la descripción de las gramáticas.
	b. Un autómata finito con transiciones lambda es un autómata no determinista.	Correcto: Las cadenas vacías lambda son aceptadas y suelen presentarse en AFND.
	c. Siempre existe un autómata finito determinista que reconoce un lenguaje reconocido por un autómata finito no determinista.
	d. No existe un autómata finito sin transiciones (lambda) que reconozca L.	Incorrecto: Si es posible este tipo de autómatas.

Parcialmente correcto

Puntos para este envío: 0.5/1.

Question9

Puntos: 1

Cuáles afirmaciones son válidas cuando se trata de analizar el funcionamiento de los Autómatas Finitos (AF):

Seleccione al menos una respuesta.

	a. Los AF son máquinas de memoria limitada.	Correcto: Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.
	b. En una máquina de estados finitos, la función de transición almacena los datos de entrada del Autómata.
	c. Los AF son máquinas de memoria amplia por ser máquinas abstractas (no reales).
	d. Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo que caracteres se han leído hasta el momento).	Correcto: Los estados son el único medio de que disponen los AF para recordar los eventos que ocurren (por ejemplo, qué caracteres se han leído hasta el momento); esto quiere decir que son máquinas de memoria limitada.

Correcto

Puntos para este envío: 1/1.

Question10

Puntos: 1

Se diseña el siguiente Autómata Finito Deterministico (AFD) para el lenguaje de palabras del alfabeto {a,b} que no tiene varias a´s seguidas. Esta solución es defectuosa porque.

Seleccione al menos una respuesta.

	a. Tiene dos finales o de aceptación q1 y q2	Incorrecto: No influye la ´parte de diseño el hecho de los dos estados de aceptación. El error se fundamenta es por la función de transición.
	b. Hay palabras como “ba”, que no tienen a´s seguidas y sin embargo no son aceptadas por el AFD.	Correcto: El "problema de diseño" de un AFD es considerar demasiadas posibilidades. El hecho que tenga dos estados finales o de aceptación no es problema y es válido en el diseño. La palabra "baba" No es aceptada por el autómata aunque sus elementos o símbolos si hacen parte del alfabeto que las compone.
	c. Hay palabras como “baa”, que tiene a´s seguidas y sin embargo son aceptadas por el AFD.
	d. Hay palabras como “baba” que no tienen a´s seguidas y sin embargo son aceptadas por el AFD pero que no pertenecen al alfabeto dado.

Parcialmente correcto

Puntos para este envío: 0.5/1.