Cuestiones
ayuda
option
Mi Daypo

TEST BORRADO, QUIZÁS LE INTERESELenguajes Formales 2 p2

COMENTARIOS ESTADÍSTICAS RÉCORDS
REALIZAR TEST
Título del test:
Lenguajes Formales 2 p2

Descripción:
Lemguajes Formales 2 p2

Autor:
Vane Sam
(Otros tests del mismo autor)

Fecha de Creación:
29/11/2022

Categoría:
Otros

Número preguntas: 70
Comparte el test:
Facebook
Twitter
Whatsapp
Comparte el test:
Facebook
Twitter
Whatsapp
Últimos Comentarios
No hay ningún comentario sobre este test.
Temario:
Enunciado adivinado: ¿Qué funciones están definidas por las siguientes reglas? A:=0B, B:=1C, B:=1, C:=0B, A:=λ f(A,0)=B, f(A,λ)=F, f(B,1)=C, f(B,1)=F, f(C,0)=B f(A,0)=B, f(A,λ)=F, f(B,1)=C, f(B,1)=F, f(C,0)=A f(B,0)=B, f(A,λ)=F, f(B,1)=C, f(B,1)=F, f(C,0)=B f(A,0)=B, f(A,λ)=F, f(C,1)=C, f(B,1)=F, f(C,0)=B.
A las gramáticas del Tipo 3 le corresponde las: Máquinas abstractas más simples. Máquinas más complejas Máquinas con memoria auxiliar.
¿A qué teorema corresponde la siguientes Proposición? "Dado un autómata finito es posible encontrar una expresión regular que denote el lenguaje representado por el autómata" En sentido inverso al teorema de síntesis se expone el teorema de análisis o problema de análisis de Kleene, que indica que dado un autómata finito es posible encontrar una expresión regular que denote el lenguaje representado por autómata. En sentido inverso al teorema Kleene, que indica que dado un autómata finito es posible encontrar una expresión regular En sentido inverso al teorema de síntesis, que indica que dado un autómata finito es posible encontrar una expresión regular que denote el lenguaje representado por autómata.
¿A qué teorema pertenece la siguiente proposición? “dado una autónoma infinita es posible encontrar una expresión regular que denote el lenguaje representado por la autónoma” En sentido inverso al teorema de sintaxis se expone el teorema de análisis o problema de análisis de Klenee. En sentido inverso al teorema de analisis En sentido inverso al teorema de Klenee .
¿Cómo influye el problema de la parada de Turing en la inteligencia artificial? Seleccione 1 (una) opción correcta Imposibilita saber si los programas inteligentes funcionaran el 100% de los casos. Posibilita saber si los programas inteligentes funcionaran el 100% de los casos. Imposibilita saber si los programas inteligentes no funcionaran el 100% de los casos.
Con un AP (autómata con pila) con aceptación por estado final, si al consumir la cadena de entrada el AP está en un estado final, pero la pila no está vacía, entonces la cadena no es aceptada Verdadero Falso.
¿Con qué tipo de problema puede clasificarse la conjetura de Collatz? Indecidible Decidible Anticipado Estructurado.
¿Cuál de las cuatro opciones enumeran los componentes de una cinta de una Maquina de Turing Universal? Seleccione 4 (cuatro) respuestas correctas. Registro Ejecución de la máquina de Turing Cinta de entrada. Registro inicial. Registro Final Pila.
¿Cuál de las siguientes afirmaciones acerca de una máquina de Turing es correcta? Se dice que todo problema computacional puede resolverse mediante una máquina de Turing, ya que estas máquinas son de mayor capacidad computacional. Se dice que no todo problema computacional puede resolverse mediante una máquina de Turing, ya que estas máquinas son de mayor capacidad computacional. Se dice que todo problema puede resolverse mediante una máquina de Turing, ya que estas máquinas son de mayor capacidad computacional.
Suponiendo un lenguaje L definido por extensión como sigue L= {X, aXa, bXb, abaXaba, abXba, baXab,...} ¿cuál es el autómata capaz de reconocerlo? Un autómata a pila Una MT Un AF.
¿Cuál de las siguientes afirmaciones es correcta? Una máquina de Turing reconoce un lenguaje L, si para toda entrada (w) L en la cinta, la máquina siempre para, y lo hace en un estado final. Una máquina de Turing reconoce un lenguaje L, si para toda entrada (w) L en la cinta, la máquina no siempre para, y lo hace en un estado final. Una máquina de Turing reconoce un lenguaje L, si para toda entrada (w) L en la cinta, la máquina siempre para, y lo hace en un estado que no es final.
¿Cuál de las siguientes afirmaciones es correcta en cuanto a una máquina de Turing universal? Una máquina de Turing universal es capaz de simular el comportamiento de cualquier máquina de Turing. Una máquina de Turing universal no es capaz de simular el comportamiento de cualquier máquina de Turing. Una máquina de Turing universal es capaz de simular el comportamiento de cualquier computadora. Una máquina de Turing universal es capaz de simular el comportamiento de cualquier AF. .
¿Cuál de las siguientes afirmaciones es verdadera? Si L1 y L2 son lenguajes regulares definidos sobre un mismo alfabeto, entonces L = L1 ∩ L2 tambien lo es. Si L1 y L2 son lenguajes regulares definidos sobre un mismo alfabeto, entonces L = L1 Y L3 tambien lo es. Si L1 y L2 son lenguajes regulares definidos sobre un mismo alfabeto, entonces L = L3 ∩ L2 tambien lo es.
Dos expresiones regulares a y B son equivalentes, (a = B), si El lenguaje que describen es el mismo: Si L(a) = L(B) El lenguaje que describen tienen los mismos símbolos: Si L(a) = L(B) El lenguaje que describen es el mismo: Si L(a) <> L(B).
¿Cuál de las siguientes siguientes afirmaciones es verdadera en relación a los lenguajes aceptados por los autómatas finitos? Los lenguajes aceptados por los autómatas finitos son fácilmente descritos por expresiones simples llamadas expresiones regulares. Los lenguajes aceptados por los autómatas finitos son fácilmente descritos por expresiones simples llamadas expresiones repetitivas. Los lenguajes aceptados por los autómatas a pila son fácilmente descritos por expresiones simples llamadas expresiones regulares.
¿Cuál de las siguientes no es modelo de máquina de Turing? La máquina analítica. La máquina sintáctica.
¿Cuál de las siguientes no es un modelo de máquina de Turing? Todas las maquinas mencionadas son variantes de la máquina de Turing, con excepción de la maquina analítica. Todas las maquinas mencionadas son variantes de la máquina de Turing, con excepción de la maquina sitáctica.
¿Cuál de las tres opciones corresponden a máquinas abstractas que resuelvan problemas computables? Seleccione 3 (tres) respuestas correctas. Autómatas a Pila Autómatas Linealmente Acotadas Máquina de Turing AFD.
¿Cuál de las siguientes proposiciones corresponde al Teorema de Síntesis? Si L es un lenguaje generado a partir de la expresión regular y entonces existe un autómata finito M tal que L = L(y) = L(M) Si L es un lenguaje generado a partir de la expresión regular y entonces existe un autómata finito M tal que L = L(y) Si L es un lenguaje generado a partir de la expresión regular y entonces existe un autómata finito M tal que L = L(M).
Una expresión es regular si: Es reconocida por un autómata de estado finito Es reconocida por un AP de estado finito Es reconocida por un AFD de estado finito Es reconocida por un AFND de estado finito.
¿Cuál de los siguientes autómatas puede reconocer el lenguaje L = {0n 1 2m 0m | m,n>0 } ? Un autómata a pila. Una MT Un AFD .
¿Cuál es el lenguaje de esta expresión? 1(01)* 1,101,101,10101,1010101,… 01, 111, 101, 10101 1, 111, 0101, 1111, 10, 100, 1000, 10000.
¿Cuál es el método que inserta un elemento en la pila de un autómata a pila? Solo 1 (una) opción es la correcta PUSH POP.
¿Cuál es el método que saca y elimina un elemento en la pila de un autómata a pila? Solo 1 (una) opción es la correcta POP PUSH.
¿Cuál es el tipo de autómata capaz de reconocer el lenguaje L={x^ny^m | n>=1} ? Un AP Una MT Un AFD Un AFND.
¿Cuál es la capacidad adicional que posee un autómata a pila? Sólo 1 (una) opción es la correcta Una pila en la que se puede almacenar una cadena de símbolos. Una cinta en la que se puede almacenar una cadena de símbolos.
Sea un autómata a pila AP y una cadena x E L(AP). Si el autómata lee la cadena x, ¿llegará necesariamente a un estado de aceptación? Si, siempre llegará a un estado de aceptación. No, no siempre llegará a un estado de aceptación.
¿Cuál es la expresión regular del lenguaje de al menos dos ceros precedidos por cualquier número de ceros seguidos de cualquier número de unos? 0*1*00 01*00 01*01*.
¿Cuál es la expresión regular que denota el lenguaje de todas las cadenas sobre el alfabeto {a,b} que contiene a una única a? b*ab* bab* b*a*b* b*(abab)*.
Cuál es la expresión regular que denota el lenguaje de todas las cadenas sobre el alfabeto {a,b} que contiene a una única cadena ba? (a+b)*ba(a+b)* (a+b)ba(a+b)* (a+b)*b*a(a+b) (a+b)*ba*(a+b)*.
¿Cuál es la secuencia básica que realiza un Autómata a Pila en cada transición? Extraer un símbolo de la pila – Pasar a un nuevo estado – Leer un símbolo de la entrada – Insertar un símbolo en la pila. Extraer un símbolo de la pila – Pasar a un nuevo estado – Insertar un símbolo en la pila. Pasar a un nuevo estado – Leer un símbolo de la entrada – Insertar un símbolo en la pila. Extraer un símbolo de la pila – Leer un símbolo de la entrada – Insertar un símbolo en la pila.
¿Cuáles de las cuatro opciones enumeran algunas de las características de una Maquina de Turing? Seleccione 4 (cuatro) respuestas correctas. Posee una cinta infinita. Reconoce lenguajes recursivamente enumerables. Puede adaptarse para que simule la lógica de cualquier… Reconoce las gramáticas irrestrictas (tipo 0). Reconoce las gramáticas irrestrictas (tipo 1).
¿Cuáles de las siguientes son una representación finita de lenguajes infinitos? Autómata finito determinista. Autómata finito no determinista. Expresión regular. Maquina Turing Autómata Linealmente Acotado.
¿Cuáles son aquellas expresiones que, aún siendo distintas, representan el mismo lenguaje? Expresiones regulares equivalentes. Expresiones regulares no equivalentes. Expresiones regulares semánticamente iguales .
¿Cuáles son las 4 (cuatro) áreas que constituyen los Fundamentos Teóricos de la Informática? Complejidad algorítmica. Computabilidad. Teoría de autómatas. Teoría de los Lenguajes Formales. Probabilidad Estadísticas Matemáticas.
Cuáles son los tres elementos que debemos tener en cuenta en un Autómata a Pila para definir una transición de un estado a otro? Selecciones 3 (tres) respuestas correctas. Estado actual. Símbolo de entrada. Símbolo que hay arriba de la pila. Símbolo de Salida.
¿Cuándo es útil el Lema de Bombeo de los lenguajes regulares? Cuando el lenguaje al que se aplica es infinito y es utilizado para demostrar que un lenguaje no es regular. Todos los lenguajes finitos son regulares o lo que es lo mismo decir que todos pueden ser representados mediante una expresión regular. Cuando el lenguaje al que se aplica es finito y es utilizado para demostrar que un lenguaje no es regular. Todos los lenguajes finitos son regulares o lo que es lo mismo decir que todos pueden ser representados mediante una expresión regular. Cuando el lenguaje al que se aplica es utilizado para demostrar que un lenguaje no es regular. Todos los lenguajes finitos son regulares o lo que es lo mismo decir que todos pueden ser representados mediante una expresión regular.
¿Cuándo un lenguaje es indecidible? Se dice q un lenguaje es indecidible si no es un leguaje recursivo. Se dice q un lenguaje es indecidible si es un leguaje recursivo.
El problema de determinar un número p que cumpla con la condición p>n para un entero n cualquiera, tal que p y p+2 sean ambos número s primos, es un problema Indecidible Decidible Complejo.
¿Cuándo una gramática ambigua es inherente? Cuando es generada por una gramática NO ambigua ( Cuando es generada por una gramática ambigua (.
Cuando una gramática falla en proporcionar estructuras únicas, decimos que esa gramática es: Ambigua No Ambigua Equivalente.
¿Cuándo una máquina de Turing M, reconoce un lenguaje L? Si al analizar una cadena de entrada se para siempre, aceptando la cadena si L, y rechazándola en caso contrario. Si al analizar una cadena de entrada no se para siempre, aceptando la cadena si L, y rechazándola en caso contrario. Si al analizar una cadena acepta la cadena L, y rechaza en caso contrario.
Suponiendo que la gramática regular G= ({0,1}, {A,B,C}, A, P) P=({A:=0B}, {A:=a}, {B:=1}, {C:=0B}, el estado inicial del autómata obtenido a partir de ella es: A Simbolos de salida Símbolos de entrada.
Dada la expresión formal de una gramática regular G={ ΣN, ΣT, S, P} es posible obtener el autómata finito AFD={Σ, Q, f, q0, F} que reconoce el lenguaje generado por ella, donde q0, el estado inicial, se obtiene a partir de: El axioma S de la gramática regular. El axioma A de la gramática regular. La producciones.
Dada la expresión formal de una gramática regular G={ ΣN, ΣT, S, P} es posible obtener el autómata finito AFD={Σ, Q, f, q0, F} que reconoce el lenguaje generado por ella, donde Q, el conjunto de estados del autómata, se obtiene a partir de: El alfabeto de los símbolos no terminales. El alfabeto de los símbolos terminales. Las transiciones.
Dada la gramática G=( {a,b}, {S,A}, S, { S::=aS|aA, a::=bA1b } ), el alfabeto de entrada del autómata finito que reconoce el lenguaje generado por la gramática es: Σ={ a, b } Σ={ a, b, c } Σ={ a, b, 0, 1 }.
Dada la siguiente gramática G = ( {S}, {0,1}, E, S ) donde P contiene las siguientes producciones: S → 0 /0S/0S1 Entonces las siguientes cadenas son generadas por G: Seleccione 4 respuestas correctas: 00000 0000001 0000111 00011 110000.
Dada la siguiente gramática G = ( {S, A}, {a, b, c}, P, S ), donde P contiene las siguientes producciones: S → A A → aAa A → bAb A → c ¿Qué cadena de las siguientes no forma parte del lenguaje generado por G? La gramática genera las cadenas del lenguaje L = {wcwR / w -> {a, b} *}, por lo que la única cadena que no forma parte de L es babacbaba La gramática genera las cadenas del lenguaje L = {wcwR / w -> {a, b} *}, por lo que la única cadena que no forma parte de L es bbabacbaba La gramática genera las cadenas del lenguaje L = {wcwR / w -> {a, b} *}, por lo que la única cadena que no forma parte de L es bbbbabacbabbbba .
Dada la siguiente máquina de Turing M… donde M acepta números en codificación unaria (…), 3 se representa por 111 y 5 por 11111. Entonces M. Computa el sucesor del número de entrada. Computa el antecesor del número de entrada.
Dada la siguiente máquina de Turing M = ({q0, q1, q2}, {0, 1}, {0, 1, +, B}, q0, δ, {q1}), donde δ está definida como δ(q0, 0) = (q0, B, D) δ(q0, 1) = (q1, B, D) δ(q1, 0) = (q1, B, D) δ(q1, 1) = (q2, B, D) δ(q2, 0) = (q2, B, D) δ(q2, 1) = (q2, B, D) La siguiente cadena forma parte del lenguaje aceptado por M: 00100 10101 110011 01010.
Dada la siguiente máquina de Turing M = ({q0, q1, q2}, {0, 1}, {0, 1, +, B}, q0, δ, {q2}), donde δ está definida como δ(q0, 0) = (q2, B, D) δ(q0, 1) = (q1, B, D) δ(q1, 0) = (q1, B, D) δ(q1, 1) = (q1, B, D) δ(q2, 0) = (q2, B, D) δ(q2, 1) = (q2, B, D) La siguiente cadena forma parte del lenguaje aceptado por M: 00110011 100110011 01110011.
Dada la siguiente máquina de Turing M = ({q0, q1, q2, q3}, {0, 1}, {0, 1, +, B}, q0, δ, {q3}), donde δ está definida como δ(q0, 0) = (q1, B, D) δ(q0, 1) = (q2, B, D) δ(q1, 0) = (q1, B, D) δ(q1, 1) = (q1, B, D) δ(q1, 1) = (q3, B, D) δ(q2, 0) = (q2, B, D) δ(q2, 1) = (q2, B, D) δ(q2, 0) = (q3, B, D) La siguiente cadena forma parte del lenguaje aceptado por M: 1010 1110 1100.
Dada la siguiente máquina de Turing M = ({q0, q1}, {0, 1}, {0, 1, +, B}, q0, δ, {q0}), donde δ está definida como δ(q0, 0) = (q1, B, D) δ(q0, 1) = (q0, B, D) δ(q1, 0) = (q0, B, D) δ(q1, 1) = (q1, B, D) La siguiente cadena forma parte del lenguaje aceptado por M: 10101010 10101111 10101011 1010101.
Dada la siguiente máquina de Turing M = ({q0, q1, q2}, {1}, {1, +, B}, q0, δ, B, {q2}), donde δ está definida como δ(q0, 1) = (q0, 1, R) δ(q0, B) = (q1, B, L) δ(q1, 1) = (q2, B, S) Cuál será el contenido de la cinta al leer la cadena "1111": 111 1010 11111 1111.
Dada la siguiente máquina de Turing M = ({q0, q1}, {1}, {1, +, B}, q0, δ, B, {q1}), donde δ está definida como: δ(q0, 1) = (q0, 1, R) δ(q0, B) = (q1, 1, S) Y donde M acepta números en codificación unaria (es decir, cada número n está representado por n unos, por ej 3 se representa por 111 y 5 por 11111). Entonces M Computa el sucesor del número de entrada Computa el antecesor del número de entrada.
Dada la siguiente máquina de Turing M = ({q0, q1, q2, q3}, {0, 1}, {0, 1, +, B}, q0, δ, {q3}), donde δ está definida como δ(q0, 0) = (q1, B, D) δ(q0, 1) = (q2, B, D) δ(q1, 0) = (q1, B, D) δ(q1, 1) = (q1, B, D) δ(q1, 1) = (q3, B, D) δ(q2, 0) = (q2, B, D) δ(q2, 1) = (q2, B, D) δ(q2, 0) = (q3, B, D) Entonces el lenguaje L aceptado por M es: L={1(0U1)*0|0(0U1)*1} L={1(0U1)*0|0(0U1)1} L={1(0U1)0|0(0U1)*1} L={1(0U1)*0|0(0U1)}.
Dada la siguiente máquina de Turing M = ({q0, q1, q2}, {0, 1}, {0, 1, +, B}, q0, δ, {q1}), donde δ está definida como δ(q0, 0) = (q0, B, D) δ(q0, 1) = (q1, B, D) δ(q1, 0) = (q1, B, D) δ(q1, 1) = (q2, B, D) δ(q2, 0) = (q2, B, D) δ(q2, 1) = (q2, B, D) Entonces el lenguaje L aceptado por M es: L={1(0U1)*/ numero de unos es 1} L={1(0U1)*/ numero de unos es 2} L={1(0U1)*/ numero de unos es 10} L={1(0U1)*/ numero de unos es 11}.
Dada la siguiente transición (p,λ,λ,q,λ) en un autómata a pila, entonces podemos afirmar que: Seleccione 4 (cuatro). El AP no extrae símbolo de la pila. El AP no inserta símbolo en la pila. El AP no avanza la cabeza de lectura. El AP pasa al estado q. El AP pasa al estado p.
Dado un autómata finito determinista AFD={Σ, Q, f, q0, F} es posible obtener la gramática G=(ΣN, ΣT, S, P), donde P se calcula según: Si f(q,a) = p entonces q:=ap Si f(q,a)=p y p pertenece a F entonces q:=a Si q0 pertenece a F entonces q0:=λ. Si f(q,a) = p entonces q:=ap Si f(q,a)=p y p pertenece a T entonces q:=a Si q0 pertenece a F entonces q0:=λ. Si f(q,a) = p entonces q:=ap Si f(q,a)=p y p pertenece a F entonces q:=a Si q0 pertenece a F entonces q0:=N.
Dado un autómata finito determinista AFD={Σ, Q, f, q0, F} es posible obtener la gramática G=(ΣN, ΣT, S, P), donde ΣN, alfabeto de los "no terminales", se obtiene a partir de: El conjunto Q de estados del autómata finito. El conjunto Q de estados finales. El conjunto N de estados del autómata finito.
De acuerdo a la jerarquía de Chomsky, los lenguajes independientes del contexto se relacionan con la siguiente Máquina abstracta AP MT AFD AFND.
De acuerdo a la jerarquía de Chomsky, los lenguajes recursivamente enumerables son aceptados por la siguiente Máquina abstracta. MT ALA AP.
De acuerdo a la jerarquía de Chomsky, los lenguajes regulares se relacionan con la siguiente Máquina abstracta: AF ALA AP.
Decimos que una gramática es Ambigua cuando: No puede proporcionar una estructura única. Puede proporcionar una estructura única. No puede proporcionar una semántica única.
Dentro de las tareas que debe realizar un compilador, ¿A qué se refiere el análisis léxico? El analizador léxico, o Scanner, lee los símbolos del programa fuente, uno a uno, desde la entrada y va formando lo que se llama tokens, que son grupos de caracteres con alguna relación entre sí. El analizador sintáctico, o Scanner, lee los símbolos del programa fuente, uno a uno, desde la entrada y va formando lo que se llama tokens, que son grupos de caracteres con alguna relación entre sí. El analizador léxico, o Scanner, lee los símbolos del programa fuente, uno a uno, desde la entrada y va formando lo que se llama señaladores, que son grupos de caracteres con alguna relación entre sí.
Dentro de las tareas que debe realizar un compilador, ¿A qué se refiere el análisis semántico? Análisis semántico, trata de determinar si el significado de las diferentes instrucciones del programa es válido. Para conseguirlo debe calcular y analizar la información asociada a las sentencias del programa. Análisis semántico, trata de determinar el orden de las instrucciones. Para conseguirlo debe calcular y analizar la información asociada a las sentencias del programa. Análisis semántico, trata de determinar el orden y la estructura de las instrucciones de un programa. Para conseguirlo debe calcular y analizar la información asociada a las sentencias del programa.
Dentro de las tareas que debe realizar un compilador, ¿A qué se refiere el análisis sintáctico? Análisis sintético, o Parser, recibe como entrada los tokens generados por el analizador léxico, comprobando además la correcta llegada en orden de los mismo. Siempre que no se haya producido errores, la salida teórica de esta fase del compilador será un árbol sintético. En el caso de que el programa sea incorrecto, se generaran los mensajes de error correspondientes. En el diseño de los analizadores sintéticos se utilizan. Análisis sintético, o Parser, no comprueba orden, solo estructura. Siempre que no se haya producido errores, la salida teórica de esta fase del compilador será un árbol sintético. En el caso de que el programa sea incorrecto, se generaran los mensajes de error correspondientes. En el diseño de los analizadores sintéticos se utilizan.
El enunciado del teorema de síntesis es "todo lenguaje aceptado por un autómata finito es regular". Verdadero Falso.
El lema del bombeo enuncia que para todo lenguaje regular finito L, existe una constante m, dependiente de ese lenguaje, de forma que si w es una cadena de L con |w| ≥ m, es posible partir w en tres cadenas x, y, z de forma que: w = xyz, |y| ≥ 1), |xy| ≥ m w = xyz, |y| ≥ 1), |xy| ≥ n w = xz, |y| ≥ 1), |xy| ≥ m.
El problema de determinar un número primo p que cumpla con la condición p>n para un entero cualquiera n, es un problema: Decidible. Comprensible. Resoluble. Indecible.
Denunciar test Consentimiento Condiciones de uso