AUTÓMATAS
AUTÓMATAS Y LENGUAJES FORMALES : Act5. quiz 1
1.
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. Las cadenas que se forman a partir de un alfabeto finito, resultan ser infinitas.
b. Dado un alfabeto, podemos formar palabras o cadenas con los símbolos del alfabeto Correcto
c. Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres. Correcto
d. Por ser un alfabeto un conjunto finito de elementos, las posibles cadenas que se formen no pueden ser vacías
2
Indique cual de las siguientes afirmaciones es la que corresponde cuando se trata de los lenguajes que puede reconoce un AF.
Seleccione una respuesta.
a. Ninguna de las afirmaciones anteriores es cierta.
b. Un automata finito determinista M reconoce un lenguaje L(M) si la coleccion de cadenas de dicho lenguaje es determinista.
c. Un automata finito determinista M reconoce un lenguaje L(M) si acepta todas las cadenas de dicho lenguaje.
d. Un automata finito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la coleccion de cadenas de dicho lenguaje. Correcto
3
Una de las siguientes afirmaciones NO aplica a los lenguajes que reconocen un autómata. Identifíquela
Seleccione una respuesta.
a. Un autómata reconoce una cadena cuando alcanza un estado de aceptacion durante su lectura Correcto
b. 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.
c. Un autómata finito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la coleccion de cadenas de dicho lenguaje.
d. 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.
4
Los ítems que encontrará a continuación constan de una afirmación VERDADERA (tesis) y dos postulados también VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si los postulados se deducen lógicamente de la afirmación y seleccionar la respuesta en su hoja de cotejo, conforme a la siguiente instrucción:
Marque A si de la tesis se deducen los postulados I y II.
Marque B si de la tesis se deduce el postulado I.
Marque C si de la tesis sólo se deduce el postulado II.
Marque D si ninguno de los postulados se deduce de la tesis.
TESIS. Los autómatas finitos determinísticos (AFD) son un subconjunto propio de los no determinísticos (AFN).
POSTULADO I. Todo AFD es un AFN
POSTULADO II. Se puede pensar entonces que los AFN son “más poderosos” que los AFD, en el sentido de que habría algunos lenguajes aceptados por algún AFN para los cuales no hay ningún AFD que los acepte
Seleccione una respuesta.
a. OPCION C
b. OPCION A Correcto
c. OPCION D
d. OPCION B
5
Las condiciones mínimas para poder describir un Autómata Finito Determinístico (DFA) son:
Seleccione al menos una respuesta.
a. Identificando el estado inicial y los estados finales Correcto
b. Identificando la función de transición. Correcto
c. Dando la lista de sus estados. Correcto
d. Identificando el alfabeto Correcto
6
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.
Seleccione una respuesta.
a. La Afirmación y la Razón son VERDADERAS pero la Razón NO es una explicación CORRECTA de la Afirmación Correcta
b. La Afirmación es VERDADERA, pero la Razón es una proposición FALSA
c. La Afirmación y la Razón son VERDADERAS y la Razón es una explicación CORRECTA de la Afirmación
d. La Afirmación es FALSA, pero la Razón es una proposición VERDADERA
7
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. OPCIÓN 3.
b. OPCIÓN 2.
c. OPCIÓN 4.
d. OPCIÓN 1.
8
Indique cual de las siguientes afirmaciones aplica correctamente a las características o definiciones de un AF.
Seleccione una respuesta.
a. En un diagrama completo que represente a un autómata finito determinista, de cada estado sale un arco por símbolo y solo uno. Correcto
b. Los autómatas finitos no deterministas son mas potentes que los autómatas finitos deterministas
c. Un autómata finito no determinista es una representación abreviada de un autómata finito determinista.
d. Ninguna de las afirmaciones anteriores es cierta
9
Los autómatas finitos no Determinísticos o no deterministas tienen las características de:
Seleccione al menos una respuesta
a. Permitir que de cada nodo del diagrama de estados salga un número de flechas mayor o menor correcto b. Las transiciones no tengan como etiqueta palabras de varias letras o hasta la palabra vacía.
c. Las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacía. correcto
d. No permitir que de cada nodo del diagrama de estados salga un número de flechas mayor o menor
10
Los palindromos (palabras capicuas) del idioma castellano, tales como "a", "y", "dad", "oso", "erre", etc., constituyen un:
Seleccione una respuesta.
a. Lenguaje estructurado por frases (en sentido estricto)
b. Lenguaje independiente del contexto (en sentido estricto)
c. Lenguaje regular Correcto
d. Es una maquina de turing.
11
Los Automatas finitos no Deterministicos tienen las caracteristicas de:
Seleccione al menos una respuesta.
a. No permitir que cada nodo del diagrama de estados salga un numero de flechas mayor o menor.
b. Las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacia. Correcto
c. Las transiciones no tengan como etiqueta palabras de varias letras o hasta la palabra vacia.
d. Permitir que de cada nodo del diagrama de estados salga un numero de flechas mayor o menor. Correcto
12
1 Un Autómata Determinístico de estados finitos (DFA), M, es una quíntupla: (Q, Σ, qi , F, δ), donde:
• Q es un conjunto finito de estados.
• Σ es un alfabeto finito.
• qi ∈ Q es el estado inicial.
• F Q son los estados finales.
• δ : (Q × Σ) → Q es la función de transición de estados.
La condición de ser Determinístico es debido a que:
Seleccione al menos una respuesta.
a. El autómata comienza en el estado inicial y lee una secuencia de símbolos (símbolo por símbolo hasta que se acabe la secuencia). Correcto
b. En cada instante lee un símbolo δ y dependiendo del símbolo y del estado s en el que se encuentra, cambia al estado dado por la función de transición: δ(s, σ) Correcto
c. Las transacciones están descritas por una función total. Correcto
d. Hay un único estado inicial. Correcto
13
Sea el vocabulario {1,2,3}, la expresión regular (1|2)* 3 indica el conjunto de todas las cadenas formadas con los símbolos 1,2 y 3 . Cuáles sentencias o cadenas son válidas :
Seleccione al menos una respuesta.
a. 2213311
b. 132211
c. 221113 Correcto
d. 121211223 Correcto
14
Los ítems que encontrará a continuación constan de una afirmación VERDADERA (tesis) y dos postulados también VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si los postulados se deducen lógicamente de la afirmación y seleccionar la respuesta en su hoja de cotejo, conforme a la siguiente instrucción:
Marque A si de la tesis se deducen los postulados I y II.
Marque B si de la tesis se deduce el postulado I.
Marque C si de la tesis sólo se deduce el postulado II.
Marque D si ninguno de los postulados se deduce de la tesis.
TESIS: El estado de un autómata es toda la información necesaria en un momento dado, para poder deducir, dado un símbolo de entrada en ese momento, cuál será el símbolo de salida.
POSTULADO I: Conocer el estado de un autómata, es lo mismo que conocer toda la historia de símbolos de entrada, así como el estado inicial, estado en que se encontraba el autómata al recibir el primero de los símbolos de entrada
POSTULADO II. La información se codifica en cadenas de símbolos, y un autómata es un dispositivo que manipula cadenas de símbolos que se le presentan a su entrada, produciendo otras tiras o cadenas de símbolos a su salida.
Seleccione una respuesta.
a. OPCION C
b. OPCION D
c. OPCION A
d. OPCION B Correcto
15
Acorde al siguiente diagrama de Moore. Identifique que expresión representa:
Seleccione una respuesta.
a. Expresión regular (ac|b)* Correcto
b. Expresión regular (bb|ab)*
c. Expresión regular (q|q )*
d. Expresión regular (ac|b|b)*
Seleccione al menos una respuesta.
a. Las cadenas que se forman a partir de un alfabeto finito, resultan ser infinitas.
b. Dado un alfabeto, podemos formar palabras o cadenas con los símbolos del alfabeto Correcto
c. Por símbolo no se está haciendo referencia a un sólo carácter. Los símbolos pueden ser nombres. Correcto
d. Por ser un alfabeto un conjunto finito de elementos, las posibles cadenas que se formen no pueden ser vacías
2
Indique cual de las siguientes afirmaciones es la que corresponde cuando se trata de los lenguajes que puede reconoce un AF.
Seleccione una respuesta.
a. Ninguna de las afirmaciones anteriores es cierta.
b. Un automata finito determinista M reconoce un lenguaje L(M) si la coleccion de cadenas de dicho lenguaje es determinista.
c. Un automata finito determinista M reconoce un lenguaje L(M) si acepta todas las cadenas de dicho lenguaje.
d. Un automata finito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la coleccion de cadenas de dicho lenguaje. Correcto
3
Una de las siguientes afirmaciones NO aplica a los lenguajes que reconocen un autómata. Identifíquela
Seleccione una respuesta.
a. Un autómata reconoce una cadena cuando alcanza un estado de aceptacion durante su lectura Correcto
b. 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.
c. Un autómata finito determinista M reconoce un lenguaje L(M) si acepta exclusivamente la coleccion de cadenas de dicho lenguaje.
d. 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.
4
Los ítems que encontrará a continuación constan de una afirmación VERDADERA (tesis) y dos postulados también VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si los postulados se deducen lógicamente de la afirmación y seleccionar la respuesta en su hoja de cotejo, conforme a la siguiente instrucción:
Marque A si de la tesis se deducen los postulados I y II.
Marque B si de la tesis se deduce el postulado I.
Marque C si de la tesis sólo se deduce el postulado II.
Marque D si ninguno de los postulados se deduce de la tesis.
TESIS. Los autómatas finitos determinísticos (AFD) son un subconjunto propio de los no determinísticos (AFN).
POSTULADO I. Todo AFD es un AFN
POSTULADO II. Se puede pensar entonces que los AFN son “más poderosos” que los AFD, en el sentido de que habría algunos lenguajes aceptados por algún AFN para los cuales no hay ningún AFD que los acepte
Seleccione una respuesta.
a. OPCION C
b. OPCION A Correcto
c. OPCION D
d. OPCION B
5
Las condiciones mínimas para poder describir un Autómata Finito Determinístico (DFA) son:
Seleccione al menos una respuesta.
a. Identificando el estado inicial y los estados finales Correcto
b. Identificando la función de transición. Correcto
c. Dando la lista de sus estados. Correcto
d. Identificando el alfabeto Correcto
6
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.
Seleccione una respuesta.
a. La Afirmación y la Razón son VERDADERAS pero la Razón NO es una explicación CORRECTA de la Afirmación Correcta
b. La Afirmación es VERDADERA, pero la Razón es una proposición FALSA
c. La Afirmación y la Razón son VERDADERAS y la Razón es una explicación CORRECTA de la Afirmación
d. La Afirmación es FALSA, pero la Razón es una proposición VERDADERA
7
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. OPCIÓN 3.
b. OPCIÓN 2.
c. OPCIÓN 4.
d. OPCIÓN 1.
8
Indique cual de las siguientes afirmaciones aplica correctamente a las características o definiciones de un AF.
Seleccione una respuesta.
a. En un diagrama completo que represente a un autómata finito determinista, de cada estado sale un arco por símbolo y solo uno. Correcto
b. Los autómatas finitos no deterministas son mas potentes que los autómatas finitos deterministas
c. Un autómata finito no determinista es una representación abreviada de un autómata finito determinista.
d. Ninguna de las afirmaciones anteriores es cierta
9
Los autómatas finitos no Determinísticos o no deterministas tienen las características de:
Seleccione al menos una respuesta
a. Permitir que de cada nodo del diagrama de estados salga un número de flechas mayor o menor correcto b. Las transiciones no tengan como etiqueta palabras de varias letras o hasta la palabra vacía.
c. Las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacía. correcto
d. No permitir que de cada nodo del diagrama de estados salga un número de flechas mayor o menor
10
Los palindromos (palabras capicuas) del idioma castellano, tales como "a", "y", "dad", "oso", "erre", etc., constituyen un:
Seleccione una respuesta.
a. Lenguaje estructurado por frases (en sentido estricto)
b. Lenguaje independiente del contexto (en sentido estricto)
c. Lenguaje regular Correcto
d. Es una maquina de turing.
11
Los Automatas finitos no Deterministicos tienen las caracteristicas de:
Seleccione al menos una respuesta.
a. No permitir que cada nodo del diagrama de estados salga un numero de flechas mayor o menor.
b. Las transiciones tengan como etiqueta palabras de varias letras o hasta la palabra vacia. Correcto
c. Las transiciones no tengan como etiqueta palabras de varias letras o hasta la palabra vacia.
d. Permitir que de cada nodo del diagrama de estados salga un numero de flechas mayor o menor. Correcto
12
1 Un Autómata Determinístico de estados finitos (DFA), M, es una quíntupla: (Q, Σ, qi , F, δ), donde:
• Q es un conjunto finito de estados.
• Σ es un alfabeto finito.
• qi ∈ Q es el estado inicial.
• F Q son los estados finales.
• δ : (Q × Σ) → Q es la función de transición de estados.
La condición de ser Determinístico es debido a que:
Seleccione al menos una respuesta.
a. El autómata comienza en el estado inicial y lee una secuencia de símbolos (símbolo por símbolo hasta que se acabe la secuencia). Correcto
b. En cada instante lee un símbolo δ y dependiendo del símbolo y del estado s en el que se encuentra, cambia al estado dado por la función de transición: δ(s, σ) Correcto
c. Las transacciones están descritas por una función total. Correcto
d. Hay un único estado inicial. Correcto
13
Sea el vocabulario {1,2,3}, la expresión regular (1|2)* 3 indica el conjunto de todas las cadenas formadas con los símbolos 1,2 y 3 . Cuáles sentencias o cadenas son válidas :
Seleccione al menos una respuesta.
a. 2213311
b. 132211
c. 221113 Correcto
d. 121211223 Correcto
14
Los ítems que encontrará a continuación constan de una afirmación VERDADERA (tesis) y dos postulados también VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si los postulados se deducen lógicamente de la afirmación y seleccionar la respuesta en su hoja de cotejo, conforme a la siguiente instrucción:
Marque A si de la tesis se deducen los postulados I y II.
Marque B si de la tesis se deduce el postulado I.
Marque C si de la tesis sólo se deduce el postulado II.
Marque D si ninguno de los postulados se deduce de la tesis.
TESIS: El estado de un autómata es toda la información necesaria en un momento dado, para poder deducir, dado un símbolo de entrada en ese momento, cuál será el símbolo de salida.
POSTULADO I: Conocer el estado de un autómata, es lo mismo que conocer toda la historia de símbolos de entrada, así como el estado inicial, estado en que se encontraba el autómata al recibir el primero de los símbolos de entrada
POSTULADO II. La información se codifica en cadenas de símbolos, y un autómata es un dispositivo que manipula cadenas de símbolos que se le presentan a su entrada, produciendo otras tiras o cadenas de símbolos a su salida.
Seleccione una respuesta.
a. OPCION C
b. OPCION D
c. OPCION A
d. OPCION B Correcto
15
Acorde al siguiente diagrama de Moore. Identifique que expresión representa:
Seleccione una respuesta.
a. Expresión regular (ac|b)* Correcto
b. Expresión regular (bb|ab)*
c. Expresión regular (q|q )*
d. Expresión regular (ac|b|b)*
.jpg)
Publicar un comentario
0 Comentarios