Quiz 1 Automatas y Lenguajes Formales


Indique cuál de las siguientes afirmaciones es la verdadera:

a. Ninguna de las anteriores.
b. Las máquinas de turing y los autómatas de pila son autómatas finitos.
c. Los autómatas finitos solo pueden aceptar lenguajes finitos.
d. Los autómatas finitos tienen un número finito de estados.

Indicar si la siguiente afirmación es verdadera o falsa: "Para todo autómata finito puede construirse una tabla de transiciones, tal que cada fila i representa un estado, cada columna j un símbolo y cada celda (i, j) contiene los posibles estados que alcanza el diagrama de transiciones cuando se encuentra en el estado i y lee el símbolo j"

Verdadero Falso

Los lenguajes aceptados por los autómatas finitos son fácilmente descritos por expresiones simples llamadas expresiones regulares, quienes les dan el nombre de conjuntos regulares a dichos lenguajes

Verdadero Falso

Indique cuál de las siguientes afirmaciones es verdadera:

a. Los autómatas finitos no deterministas son más potentes que los autómatas finitos deterministas
b. Ninguna de las afirmaciones anteriores es cierta
c. En un diagrama completo que represente a un autómata finito determinista, de cada estado sale un arco por símbolo y solo uno.
d. Un autómata finito no determinista es una representación abreviada de un autómata finito determinista.

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

a. Un autómata de pila determinista
b. Una máquina de Turing.
c. Un autómata finito
d. Un autómata de pila no determinista

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:

a. Lenguajes de Programación
b. Compiladores
c. Aplicaciones de Computador
d. Procesadores de texto

Los palíndromos (palabras capicúas) del idioma castellano, tales como "a", "y", "dad", "oso", "erre", etc., constituyen un:

a. Lenguaje estructurado por frases (en sentido estricto)
b. Es una máquina de turing.
c. Lenguaje independiente del contexto (en sentido estricto)
d. Lenguaje regular

Indique cuál de las siguientes afirmaciones es FALSA:

a. Un autómata finito determinista utilizado como reconocedor de lenguajes con al menos una cadena necesariamente tiene que tener al menos un estado de aceptación.
b. Un autómata reconoce una cadena cuando alcanza un estado de aceptación durante su lectura
c. Un autómata finito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la colección de cadenas de dicho lenguaje.
d. Dada una gramática regular G, siempre existe un autómata finito M tal que L(G) = L(M) y M tiene un único estado de aceptación.

Indique cuál de las siguientes afirmaciones es Falsa:

a. En un autómata finito determinista para cada estado existe exactamente una transición por cada símbolo del alfabeto de la máquina.
b. En un autómata finito no determinista puede haber cero, una o más transiciones desde un estado leyendo el mismo símbolo de entrada que conduzcan a estados diferentes (o posiblemente al mismo).
c. Para un autómata finito no determinista siempre podrán recorrerse una o más rutas distintas al leer una cadena dada, y por tanto todas deberán examinarse para verificar si alguna termina en un estado de aceptación.
d. Los autómatas finitos tienen un número finito de estados.  

Los autómatas finitos se utilizan generalmente para:

a. Verificar que las cadenas pertenecen al lenguaje    
b. Reconocer todo tipo de lenguajes    
c. Como un analizador en la traducción de algoritmos al computador.                
d. No tienen un uso habitual en la computación práctica actual.              

En un contexto general un Lenguaje lo podemos definir como:

a. Un Sistema de Símbolos Convencionales, hablados o escritos con el que nos comunicamos             
b. Significado de las cadenas que lo componen               
c. Conjunto de instrucciones que indican acciones a realizar     
d. Estudio de las reglas y principios que regulan su uso                

Uno de los principales factores determinantes en la revolución en el ámbito de la ciencia, la técnica y la cultura de nuestros días es el desarrollo de la Informática PORQUE Un lenguaje natural como el inglés o el español son la clase de lenguajes que han evolucionado con el paso del tiempo y tienen por fin la comunicación humana.

a. La Afirmación y la Razón son VERDADERAS y la Razón es una explicación CORRECTA de la Afirmación
b. La Afirmación es FALSA, pero la Razón es una proposición VERDADERA
c. La Afirmación es VERDADERA, pero la Razón es una proposición FALSA
d. La Afirmación y la Razón son VERDADERAS pero la Razón NO es una explicación CORRECTA de la Afirmación

A continuación encuentra un listado de los que pueden ser lenguajes formales, seleccione cuáles son:

a. El conjunto de todos los programas no válidos en un determinado lenguaje de programación.
b. El conjunto de todas las palabras sobre {a}
c. El conjunto de entradas para las cuales una particular máquina de Turing se detiene.
d. El conjunto {an: n es un número primo}

Los Autómatas finitos no Determinísticos tienen las características de:

a. No permitir que cada nodo del diagrama de estados salga un número de flechas mayor o menor.
b. Las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacía.
c. Las transiciones no tengan como etiqueta palabras de varias letras o hasta la palabra vacía.
d. Permitir que de cada nodo del diagrama de estados salga un número de flechas mayor o menor.

Los autómatas se pueden representar mediante:

a. El conjunto de tablas representativas
b. El conjunto de entradas de una máquina de turing
c. Diagrama de Moore
d. Tablas de transiciones

Calificación: 20,8/25