1. Cuando se habla de equivalencia de autómatas finitos determinísticos y autómatas finitos no determinísticos, es válido afirmar:
a. Un AFD es equivalente a un AFND si el número d etransiciones es igual, independiente del número de estados.
b. La equivalencia de un AFD y un AFND se da solo evaluando el tipo de símbolos que componen el alfabeto.
c. La equivalencia de un AFND y un AFD, obliga a que tengan el mismo número de estados
d. os autómatas finitos determinísticLos (AFD) son un subconjunto propio de los no determinísticos (AFN)
2. Acerca de la Equivalencia de AFD Y AFN es válido afirmar.
a. Para covertir u AFD a u AFND, el AFD debe tener menos estados que el AFND
b. Todo Autómata por defecto es No determinístico
c. Todo Autómata por defecto es Determinístico.
d. Los autómatas finitos determinísticos (AFD) son un subconjunto propio de los no determinísticos (AFN)
3. 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.
a. Es un Autómata Finito Determinístico (AFD)
b. El lenguaje reconocido por el autómata es: a (b* | a* ) ba*
c. El lenguaje reconocido por el autómata es: a (b*b | a*b) a*
d. Es un Autómata Finito Determinístico con lambda - transiciones
4. Cuando se habla de Expresiones Regulares, son válidas las siguientes apreciaciones:
a. Las ER son simplemente fórmulas cuyo propósito es representar cada una de ellas un lenguaje
b. Una expresión regular es la representación de la cadena más característica del lenguaje respectivo
c. El significado de una ER es simplemente el lenguaje que ella representa.
d. Una ER representa los símbolos y el alfabeto que denota las características de un autómata.
5. El número mínimo de estados de un autómata finito no determinista es:
a. Dos
b. No hay número mínimo
c. Depende del alfabeto sobre el que está definido.
d. Uno
6. Indique cual de las siguientes afirmaciones referidas a los autómatas de la figura, son ciertas. (Observe que hay una transición lambda que no lee ningún símbolo de la cadena de entrada):
a. 1. Los autómatas reconocen el lenguaje formado por todas las cadenas que empiezan por 1 y que no terminan en dos ceros consecutivos.
b. 4. Cualquier autómata no determinista que reconozca el mismo lenguaje que el autómata B tiene al menos cuatro estados.
c. 2. Ambos autómatas reconocen el mismo lenguaje incluyendo la cadena vacía.
d. 3. El autómata A es más potente por ser No Determinista.
7. Cuando se define un autómata finito se puede construir o recrear mediante las tablas de transiciones. Al respecto indique cuál afirmación respecto a la creación de tablas de transición es válida:
a. La fila i representa los símbolos. La Columna j representa los estados y cada celda (i,j) los posibles estados que alcanza el diagrama de Moore que es el que genera la tabla de transición.
b. La fila i representa los estados. Las columnas j representan los símbolos. Cada celda (i,j) los posibles estados que alcanza el diagrama de transiciones cuando se encuentra en el estado i y lee el símbolo j.”
c. En una tabla de transición, no se representa el estado inicial ya que este se ubica en la primera celda (i,j) de la tabla.
d. El estado final en una tabla de transición se identifica mediante el símbolo de interrogación. este puede ubicarse en cualquier celada (i,j)
8. Un autómata finito con landa transiciones es:
Seleccione al menos una respuesta.
a. Un autómata al que se le permite cambiar de estado sin necesidad de consumir un símbolo de entrada
b. Un autómata con menor número de estados
c. Un AFND
d. Un AFD
9. Indique cuál de las siguientes afirmaciones referidas a lenguajes del alfabeto ∑ = {0,1,2} son ciertas:
a. Si L es un lenguaje regular también lo es el lenguaje consistente en las inversas de las cadenas de L
b. No existe ningún autómata determinista que reconozca el lenguaje de las cadenas en las que toda pareja de 0´s contiguos aparece antes de cualquier pareja de 1´s contiguos.
c. El lenguaje de las cadenas equilibradas con igual número de 0´s y de 1´s tales que ningún prefijo de cualquiera de ellas posee más de dos 0´s que 1´s ni más de dos 1´s que 0´s es un lenguaje regular.
d. El lenguaje de las cadenas con a lo sumo una pareja de 0´s consecutivos y a los sumo una pareja de 1´s consecutivos no es regular.
10. Indique cuál de las siguientes afirmaciones se apropia a los conceptos de los Autómatas Finitos:
a. Las máquinas de Turing y los autómatas de pila son autómatas finitos
b. Ninguna de las afirmaciones anteriores es cierta
c. Los autómatas finitos sólo pueden aceptar lenguajes finitos.
d. Los autómatas finitos tienen un número finito de estados.
CALIFICACIÓN 22,5 / 25
