Quiz1_Automatas_2015 2

23/10/2015

campus13 2015­2
AUTOMATAS Y LENGUAJES FORMALES 301405A_224

Perfil

Salir

 

Quiz1
1
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. Operación cerrada de dos lenguajes
b. Asociación de lenguajesc. Concatenación (representada por un punto)
d. Unión de lenguajes

2
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 con lambda transicionesb. El lenguaje reconocido por el autómata es: a (b*b | a*b) a*
c. El lenguaje reconocido por el autómata es: a (b* | a* ) ba*
d. Es un Autómata Finito Determinístico (AFD)

3

Sea L el lenguaje de alfabeto Σ = {a,b,c} y cadenas de forma wcv, donde w y v son cadenas de a’s y b’s y w y v tienen la misma

Puntos: 1

longitud pero v no es la cadena inversa de w. Dicho lenguaje coincide con el generado por la gramática:
Seleccione una
respuesta.a. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb, R→aRb, R→bRa, R→c.
b. S → aSa, S→bSb, S→aRb, S→bRa, R→bRb, R→aRa, R→bRa, R→c.
c. S → aSa, S→bSb, S→aRb, S→bRa, R→aRa, R→bRb, R→c.
d. S → aSa, S→bSb, S→aRb, S→bRa, R→aRb, R→bRa, R→c.

4
Puntos: 1

Cuando se trata de simplificar Autómatas, se deben tener en cuenta aspectos como: (Identifique cuál paso o concepto es válido en este
proceso de Minimización).Seleccione una
respuesta.

a. Minimización abarca el concepto de reducir lenguajes
b. Para saber si dos estados q1 y q2 son equivalentes, se les pone a ambos como estado final de los autómatas M1 y M2, y se
procede a comparar dichos autómatas. Si estos últimos son equivalentes, quiere decir que los estados q1 y q2 son equivalentesc. Dos estados son distinguibles si son compatibles (es decir, si ambos son finales o ambos son iníciales).
d. Dos estados son distinguibles si por ejemplo uno es final y el otro es inicial

5

Dado el siguiente Autómata Finito (AF).

Puntos: 1

Identifique las propiedades válidas que corresponden al autómata
Seleccione al menos
una respuesta.

a. Es un AFND
b. ER= xx*zx((zx+x*z)x)*
c. Ya es un autómata mínimo y no permite más reducción.
d. ER= xx*zx((z+xx*z)x)*http://campus13.unad.edu.co/campus13_20152/mod/quiz/attempt.php?id=6002

1/4

23/10/2015

6

campus13 2015­2

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

Puntos: 1

Seleccione al menos
una respuesta.

a. El autómata A es un AFND y reconoce el mismo lenguaje que el autómata Bb. Ambos autómatas reconocen el mismo número de posibles cadenas válidas
c. El autómata A es “equivalente” al autómata B
d. Una misma ER aplica a ambos autómatas

7

1. Cuál es la longitud de dos cadenas o palabras concatenadas (propiedad de la concatenación):

Puntos: 1

Seleccione una
respuesta.

a. |w.u| =|w| . |u| para todo w,u que pertenezca a ∑*
b. |w.u| =|w| + |u| para todo w,u que pertenezca a ∑
c. |w.u| =|w| + |u| para todo w,u que pertenezca a ∑*d. |w.u| =|w|*+ |u|* para todo w,u que pertenezca a ∑

8
Puntos: 1

La minimización de Autómatas, es un ejercicio común en Automatización. Identifique que conceptos son
válidos cuando se aplica este proceso:
Seleccione una
respuesta.

a. La minimización no debe cambiar el lenguaje aceptado pero si las posibles cadenas válidasb. En un proceso de minimización se pueden eliminar estados distinguibles entre si, siempre y cuando cumplan las condiciones
de aceptación de lenguaje.
c. En un proceso de minimización se pueden eliminar estados No distinguibles entre si, siempre y cuando cumplan las
condiciones de aceptación de lenguaje
d. Un autómata se puede minimizar siempre y cuando el autómata dado no acepte cadenas vacías.

9...