Quiz 1 Automatas Y Lenguajes Formales

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:

...