AUTÓMATAS Y LENGUAJES FORMALES: Act 4. Lección Evaluativa1

Todas Correctas

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. Hay palabras como “ba”, que no tienen a´s seguidas y sin embargo no son aceptadas por el AFD Correcto
 b. Tiene dos finales o de aceptación q1 y q2 .

 c. Hay palabras como “baa”, que tiene a´s seguidas y sin embargo 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. 

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. 

2 

La expresión regular que se asocia la siguiente autómata es: 

 Seleccione una respuesta. 

 a. r = (10) * + 1* 

 b. r = (1 + 0) + 1*

 c. r = (10 + 0) * Correcto Correcto: Las cadenas que tengan varios unos consecutivos son rechazadas. 

 d. r = (1)* + (0) + lambda 

3 

Un autómata finito con landa transiciones es: 

Seleccione al menos una respuesta. 

 a. Un AFND Correcto

 b. Un AFD Incorrecto

 c. Un autómata con menor número de estados

 d. Un autómata al que se le permite cambiar de estado sin necesidad de consumir un símbolo de entrada Correcto 

 4

Acerca de la cadena vacía lambda se puede afirmar que: 

 Seleccione una respuesta. 

 a. Es un palíndromo Correcto

 b. Es un símbolo y no es parte de un lenguaje

 c. No es una cadena sino un símbolo 

 d. Es un Autómata finito (AF) 

5 

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: 

Seleccione una respuesta. 

 a. 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. 

 b. 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) 

 c. 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.

 d. 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.” Correcto Esto es lo mismo que describir el diagrama de transiciones completo. 

6 

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. El lenguaje reconocido por el autómata es: a (b* | a* ) ba* Correcto Correcto. Esta ER es válida 

 b. El lenguaje reconocido por el autómata es: a (b*b | a*b) a* Correcto Correcto. Esta ER es válida 

 c. Es un Autómata Finito Determinístico con lambda - transiciones 

 d. Es un Autómata Finito Determinístico (AFD) Incorrecto Es un AFND.

7 

Acerca de la Equivalencia de AFD Y AFN es válido afirmar. 

Seleccione una respuesta. 

 a. Los autómatas finitos determinísticos (AFD) son un subconjunto propio de los no determinísticos (AFN) Correcto

 b. Para covertir u AFD a u AFND, el AFD debe tener menos estados que el AFND 

 c. Todo Autómata por defecto es Determinístico. 

d. Todo Autómata por defecto es No determinístico 

8 

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 f por la tabla siguiente: 

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

 Seleccione una respuesta. 

 a. 1(01) * Correcto: La expresión regular genera las cadenas que inician con 1 y que luego pueden o no tener un 0 o un 1 . 

 b. 0(010)* 

 c. 1*(1) 

 d. 1( 1) (0)* 

 9

Que representa la siguiente figura:

 Seleccione una respuesta. 

 a. No representa un autómata válido por que el mismo estado inicial es el mismo estado final. 

 b. Un Autómata de tipo AFND válido Correcto: Es una extensión válida de un AFD. 

 c. Un Autómata que acepta palabras o cadenas que contienen únicamente b´s 

 d. No representa un autómata válido por que tiene un solo estado. 

10 

 Cuando se habla de equivalencia de autómatas finitos determinísticos y autómatas finitos no determinísticos, es válido afirmar: 

Seleccione una respuesta. 

 a. La equivalencia de un AFD y un AFND se da solo evaluando el tipo de símbolos que componen el alfabeto. 

 b. Un AFD es equivalente a un AFND si el número de transiciones es igual, independiente del número de estados. 

 c. os autómatas finitos determinístic Los (AFD) son un subconjunto propio de los no determinísticos (AFN) Correcto

 d. La equivalencia de un AFND y un AFD, obliga a que tengan el mismo número de estados