AUTÓMATAS Y LENGUAJES FORMALES: Act 3. Reconocimiento unidad 1

1. Dado un alfabeto A, una cadena sobre A es una sucesión de longitud finita (mayor o igual a cero) de símbolos del alfabeto. La letra griega lambda, , se usa para denotar:

Seleccione una respuesta.

 a. El lenguaje que suma todas las cadenas
 b. Un lenguaje infinito
 c. El lenguaje cuyo único elemento es la cadena nula Correcto
 d. El lenguaje vacío.

2 

Un diagrama de Moore o de Transición de Estados representa una abstracción de un modelo matemático de un Autómata, siendo análogo a ____________, que representa la abstracción de una Máquina usada en procesos automatizados. 

 Seleccione una respuesta. 

 a. La instrucciones de operación de la Máquina 

 b. Las características de color de la máquina 

 c. El plano del diseño de la máquina  Correcto: Los diagramas de Moore son otra forma de representar las funciones de transición y salida de un autómata. 

 d. Las características técnicas de la Máquina 

3 

 Se denomina cadena, palabra o frase a una secuencia finita de símbolos de un alfabeto ∑. Estas cadenas son denotadas como w. 

Dado el siguiente autómata finito determinístico (AFD) 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 pertenece Q es el estado inicial. 

 · F incluye Q es el conjunto de estados finales. 

 Y que para el ejercicio ∑ = {a,b} Q ={ q0, q1} F = {q1} se representa mediante el siguiente diagrama de Moore: Automata 

 El conjunto de palabras aceptadas por este autómata son: 

 Seleccione una respuesta. 

 a. Todas las palabras que terminan en a y que estén precedidas por una b 

 b. {w a | w ϵ {a,b} potencia 2 } 

 c. {w a | w ϵ {a,b}* }   Correcto: El conjunto de palabras aceptadas por este autómata son la palabras que terminan en a. 

 d. Todas las palabras que terminan en dos a´s 

4

Dado el alfabeto: ∑= {a,b} una representación válida de la expresión regular y su lenguaje sería: 

 Seleccione una respuesta. 

 a. Expresión Regular (bb)* Como Lenguaje: { Ø,b,bbb,bbbbbb,…} 

 b. Expresión Regular (a+b)*a Como Lenguaje: empiezan en a y terminan en b

 c. Expresión Regular a(a+b)*a + b(a+b)*b Como Lenguaje: empiezan en a y terminan en ba 

d. Expresión Regular a.(a+b)* Como lenguaje: {a,aa,ab,aaa,aab,aba,abb, …} Correcto El cierre de Kleene de un lenguaje es la unión de todas las potencias de este lenguaje. 

5 

 La “Teoría de Lenguajes”, define bloques constructores de lenguaje. El bloque más sencillo es el alfabeto. De las siguientes afirmaciones cuales definen o son verdaderas con respecto a un “alfabeto” Pueden haber varias opciones válidas 

Seleccione al menos una respuesta. 

 a. { α , α , …, α } Es un ejemplo de alfabeto. Correcto

 b. Los símbolos pueden ser nombres. Correcto

 c. Por símbolo, no se está haciendo referencia a un solo carácter. Correcto

 d. Los alfabetos son finitos. Correcto 

Todas las respuestas son verdaderas.

Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está esta haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres. 

 Lenguaje Formal: Un alfabeto es un conjunto finito de símbolos. De esta definición se debe resaltar lo siguiente. (1) Los alfabetos son finitos. (2) Por símbolo no se está esta haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres. Todas las respuestas son verdaderas. 

6 

Los lenguajes se pueden clasificar según el tipo de dispositivos de aceptación y generación que existen para ellos. Con respecto a esto, asocie correctamente los siguientes textos: