Act 5 Quiz De Automatas

Para el siguiente autómata, M =(Q, A, q1 , δ, F) donde:

Q = { q1 , q2 , q3 , q4 }

A = {a, b}

Cuáles igualdades son válidas para la función de transición δ

OPCION1. δ (q2 , a ) = q2 δ (q2 , b ) = q3

OPCION2. δ (q4 , a ) = q4 δ (q4 , b ) = q4

OPCION3. δ (q3 , a ) = Ǿ δ (q3 , b ) = q3

OPCION4. δ (q1 , a ) = q2 δ (q1 , b ) = q4

Seleccione al menos una respuesta.

a. OPCION 2.

b. OPCION 1.

c. OPCION 4.

d. OPCION 3.

2

Indicar cuál es el tipo de autómata más sencillo (menos potente) capaz de reconocer el lenguaje {xnymzn | n>=25, m>=50}.

Seleccione una respuesta.

a. Un autómata finito

b. Una máquina de Turing.

c. Un autómata de pila no determinista

d. Un autómata de pila determinista

3

Teniendo en cuenta que podemos definir un Autómata como una máquina conceptual o teórica para el reconocimiento de patrones, entonces los siguientes componentes: Analizados Léxico, Analizador Sintáctico y Generador de Código corresponderían a una aplicación de un Autómata en el la implementación de:

Seleccione una respuesta.

a. Lenguajes de Programación

b. Compiladores

c. Aplicaciones de Computador

d. Procesadores de texto

4

Un alfabeto es un conjunto finito de símbolos. De esta definición podemos afirmar correctamente: (Seleccione dos de las afirmaciones que sean correctas).

Seleccione al menos una respuesta.

a. Por ser un alfabeto un conjunto finito de elementos, las posibles cadenas que se formen no pueden ser vacías

b. Las cadenas que se forman a partir de un alfabeto finito, resultan ser infinitas.

c. Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres.

d. Dado un alfabeto, podemos formar palabras o cadenas con los símbolos del alfabeto

5

Para comprender la definición de Autómata Finito, se suele asociar el concepto al de una “Máquina” que evoca un aparato metálico usualmente ruidoso, mecánico y que ejecuta tareas repetitivas que requieren de mucha fuerza o velocidad combinadas con precisión. Cuales serían características de los Autómatas Finitos:

Seleccione al menos una respuesta.

Seleccione al menos una respuesta.

a. Las máquinas de Turing y los autómatas de pila son autómatas finitos.

b. Los autómatas finitos son capaces de reconocer solamente un determinado tipo de lenguajes, llamados “lenguajes Regulares”.

c. Los autómatas finitos tienen un número finito de estados.

d. Los autómatas finitos solo pueden aceptar lenguajes finitos.

6

3. Partiendo de la definición de que un Autómata Finito Determinístico (AFD) está dado por la quíntupla: A = (Q, ∑, f, q0 , F) donde:

• Q es un conjunto de estados.

• ∑ es el alfabeto de entrada

• f: Q X ∑ → Q es la función (total) de transición.

• q0 que pertenece a Q es el estado inicial.

Y que para el ejercicio, el autómata acepta las cadenas (01) n 1) :

,

A = ({q0 , q1 , q2 , q3 } , {0,1} , f , q0 , { q2 })

Representado mediante el grafo:

La tabla de transición correspondiente es:

Seleccione una respuesta.

a. TABLA DE TRANSICION C

b. TABLA DE TRANSICION B

c. TABLA DE TRANSICION D

d. TABLA D ETRANSICION A

7

Las cadenas no nulas, en un alfabeto Σ se crean por: (selecciones dos opciones de respuesta).

Seleccione al menos una respuesta.

a. Longitud mínima del alfabeto unida al número máximo de combinaciones.

b. Intersección de los valores de lambda

c. En un alfabeto no existen cadenas “no nulas”

d. Concatenación de cadenas sencillas, las de longitud 1.

...