Lenguajes Formales y Computabilidad Parcial 2 Siglo 21

Suponiendo el siguiente autómata finito: AF= ({0, 1}, {C0,C1,C2,C3,C4}, C0, f, {C2,C4}). El alfabeto de los símbolos terminales de gramática regular obtenida a partir de el es:

Seleccione las 4 (cuatro) opciones correctas. La expresión formal de una máquina de Turing, ¿Qué incluye?

Seleccione las 4 (cuatro) opciones correctas. ¿Cuáles de las siguientes operaciones realiza una máquina de Turing durante una transición?

¿Cuál de las siguientes afirmaciones es verdadera en relación al lema de bombeo?

La expresión formal de un autómata a pila es: AP= (Σe, Q, Γ, qo, zo, f, F), donde Σe representa...

En una máquina de Turing los símbolos de entrada:

Para el autómata cuyo diagrama de estados se presenta en la siguiente imagen, las ecuaciones características son:

Seleccione las 2 (dos) opciones correctas. El lenguaje aceptado por un autómata a pila puede ser caracterizado como:

¿Cuál es el tipo de autómata capaz de reconocer el lenguaje L={x^n y^m | n>1}?

Seleccione las 4 (cuatro) opciones correctas. ¿Cuáles de las siguientes son expresiones correctas?

Suponiendo un lenguaje L definido por extensión como sigue L =(λ, aλa, bλb, abaλaba, abλba, baλab,...) ¿Cuál es el autómata capaz de reconocerlo?

En una máquina de Turing la función de transición de estados se representa como:

Seleccione las 4 (cuatro) opciones correctas. En un autómata a pila, en cada transición, el autómata cambia de estado y acciona sobre la pila. ¿Cuáles de las siguientes son operaciones válidas sobre la pila?

Una máquina de Turing es un modelo matemático consistente en un autómata que es capaz de implementar cualquier problema matemático expresado a través de un algoritmo.

Las transiciones en un autómata a pila dependen de:

Una máquina de Turing actúa como reconocedor cuando:

Si se parte de la expresión formal de una gramática regular el autómata finito obtenido es:

Dada la expresión formal de una gramática regular G=(ΣΝ, ΣΤ, 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:

Seleccione las 3 (tres) opciones correctas. ¿Cuáles de las siguientes afirmaciones son verdaderas en relación al lema del bombeo?

Suponiendo que es necesario reconocer las cadenas del lenguaje formado por las cadenas sobre el alfabeto {0,1} que tienen igual cantidad de 1's y 0's. ¿Qué tipo de autómata se debería usar?

Una máquina de Turing actúa como un traductor cuando:

El lema de bombeo enuncia que para todo lenguaje regular infinito 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:

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:

¿Cuál de las siguientes opciones se caracteriza por describir todas las cadenas que se pueden reconocer desde un estado dado en un autómata finito?

Los lenguajes aceptados por los autómatas a pila son:

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 ΣT, el conjunto de estados del autómata se obtiene a partir de:

Un arco del diagrama de estados de un autómata a pila, que conecta a los estados p y q, y está etiquetado con a, a/λ, significa que:

¿Cuál es el número mínimo de estados que debe tener una máquina de Turing para que acepte alguna cadena?

Sea el vocabulario (a, b) y la expresión regular aabb, ¿Cuál es el lenguaje denotado?

Partiendo de un autómata finito determinista puede obtenerse:

Si para un autómata A, sus ecuaciones características son: X0 = a X1, X1 = b X2 + a X1 + b y X2 + b + λ. Resolviendo x1 se obtiene que:

Los teoremas de Kleene que demuestran la equivalencia entre expresiones regulares y autómatas finitos son:

¿Cuál de las siguientes afirmaciones es verdadera en relación al lema de bombeo?

La información almacenada durante la ejecución de un autómata a pila...

Toda máquina de Turing posee:

El problema de la parada o el problema de la detención para máquinas de Turing es un:

Un lenguaje se dice inherentemente ambiguo si:

Si para un autómata A, sus ecuaciones características son: X0 = a X1, X1 = b X2 + a X1 + b y X2 = b X2 + b + λ. Resolviendo x2 se obtiene que:

Si para un autómata A, sus ecuaciones características son: X0 = a X1, X1 = b X2 + a X1 + b y X2 = b X2 + b + λ. Resolviendo x0 se obtiene que:

G = ({0,1}, {A, B, C}, A, P) P = ((A:=0B), (A:= ), (B:=1C), (B:=1), λ (C:=0B). El conjunto de estados del autómata obtenido a partir de ella es:

¿Cuál es el tipo de autómata capaz de reconocer el lenguaje L = { xⁿym| n>1}?

Si es un autómata finito, q0 es el estado inicial, ¿Qué se obtiene resolviendo su ecuación característica x0?

El lenguaje aceptado por un autómata a pila puede ser caracterizado como:

¿Cuál de las siguientes es una característica de los autómatas finitos?

Los lenguajes aceptados por los autómatas finitos son fácilmente descritos por expresiones complejas llamadas expresiones compuestas.

¿Cuáles de las siguientes opciones se relacionan con características de una máquina de Turing?

Las transiciones en un autómata a pila dependen de:

En una máquina de Turing que verifique si una cadena pertenece al lenguaje L = {w#w} | w ∈ {0,1}, el alfabeto de entrada debe ser:

¿Cuál es el lenguaje denotado por la siguiente expresión regular 0* 10?

La expresión formal de una máquina de Turing, donde Γ representa:

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 ΣT, alfabetos de los terminales, se obtiene a partir de:

Una máquina de Turing es un modelo matemático consistente en un autómata que es capaz de implementar cualquier problema matemático expresado a través de un algoritmo.

¿Cuál es la expresión regular que denota el lenguaje de todas las cadenas sobre el alfabeto {a, b} que comiencen con b?

¿Cuál de los siguientes autómatas puede reconocer el lenguaje L = {0^n 1^(2m) 0^m | m, n > 0}?

¿Cuál es la expresión regular que denota el lenguaje de todas las cadenas sobre el alfabeto {a, b} que contienen la cadena ba?

¿Cuál de las siguientes afirmaciones es correcta en referencia a la precedencia de operadores en una expresión regular?

¿Cuál de las siguientes afirmaciones es correcta?

En una máquina de Turing la función de transición de estados se representa como:

A diferencia de los autómatas finitos, los autómatas a pila cuentan con:

A las gramáticas del Tipo 3 le corresponde las:

¿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'

¿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”

¿Cómo influye el problema de la parada de Turing en la inteligencia artificial? Seleccione 1 (una) opción correcta

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

¿Con qué tipo de problema puede clasificarse la conjetura de Collatz?

¿Cuál de las cuatro opciones enumeran los componentes de una cinta de una Maquina de Turing Universal? Seleccione 4 (cuatro) respuestas correctas.

¿Cuál de las siguientes afirmaciones acerca de una máquina de Turing es correcta?

¿Cuál de las siguientes afirmaciones acerca de una máquina de Turing es verdadera?

¿Cuál de las siguientes afirmaciones es correcta en cuanto a una máquina de Turing universal?

¿Cuál de las siguientes afirmaciones es verdadera?

Dos expresiones regulares a y B son equivalentes, (a = B), si

¿Cuál de las siguientes afirmaciones es verdadera en relación a los lenguajes aceptados por los autómatas finitos?

¿Cuál de las siguientes no es modelo de máquina de Turing?

¿Cuál de las tres opciones corresponden a máquinas abstractas que resuelvan problemas computables? Seleccione 3 (tres) respuestas correctas.

¿Cuál de las siguientes proposiciones corresponde al Teorema de Síntesis?

Una expresión es regular si:

¿Cuál es el lenguaje de esta expresión? 1(01)*

¿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

¿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

¿Cuál es el resultado de la operación de la siguiente máquina de Turing?

¿Cuál es la capacidad adicional que posee un autómata a pila? Sólo 1 (una) opción es la correcta

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?

¿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?

¿Cuál es la expresión regular del lenguaje reconocido por el autómata?

¿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?

¿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?

¿Cuál es una expresión regular correcta para el lenguaje reconocido por el autómata cuyo diagrama se muestra en la siguiente imagen?

¿Cuál es una expresión regular correcta para el lenguaje reconocido por el autómata cuyo diagrama se muestra en la siguiente imagen?

¿Cuál es una expresión regular correcta para el lenguaje reconocido por el autómata cuyo diagrama se muestra en la siguiente imagen?

¿Cuál es la secuencia básica que realiza un Autómata a Pila en cada transición?

¿Cuáles de las cuatro opciones enumeran algunas de las características de una Maquina de Turing? Seleccione 4 (cuatro) respuestas correctas.

¿Cuáles de las cuatro opciones enumeran los componentes de una cinta de una Máquina de Turing Universal? Seleccione las 4 (cuatro) respuestas correctas.

¿Cuáles de las siguientes son una representación finita de lenguajes infinitos?

¿Cuáles son aquellas expresiones que, aún siendo distintas, representan el mismo lenguaje?

¿Cuáles son las 4 (cuatro) áreas que constituyen los Fundamentos Teóricos de la Informática?

¿Cuáles de las 4 (cuatro) opciones enumera algunas características de las Maquinas de Turing?

¿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.

¿Cuándo es útil el Lema de Bombeo de los lenguajes regulares?

¿Cuándo un lenguaje es indecidible?

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úmeros primos, es un problema:

¿Cuándo una gramática ambigua es inherente?

Cuando una gramática falla en proporcionar estructuras únicas, decimos que esa gramática es:

¿Cuándo una máquina de Turing M, reconoce un lenguaje L?

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 f se calcula según lo siguiente:

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:

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:

Dada la gramática G=( {a,b}, {S,A}, S, { S::=aS|aA, A::=bA|b } ), el alfabeto de entrada del autómata finito que reconoce el lenguaje generado por la gramática es:

Dada la siguiente gramática G = ( {S}, {0,1}, S, P ) donde P contiene las siguientes producciones: S → 0 /0S/0S1 Entonces las siguientes cadenas son generadas por G: Seleccione 4 respuestas correctas:

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?

Dada la siguiente máquina de Turing M, cuál sería el contenido de la cinta al leer la cadena “1111”

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.

Dada la siguiente máquina de Turing M, entonces M…

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:

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:

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:

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:

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":

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:

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:

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:

Dada la siguiente transición (p,λ,λ,q,λ) en un autómata a pila, entonces podemos afirmar que: Seleccione 4 (cuatro).

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:

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:

De acuerdo a la jerarquía de Chomsky, los lenguajes independientes del contexto se relacionan con la siguiente Máquina abstracta:

De acuerdo a la jerarquía de Chomsky, los lenguajes recursivamente enumerables son aceptados por la siguiente Máquina abstracta.

De acuerdo a la jerarquía de Chomsky, los lenguajes regulares se relacionan con la siguiente Máquina abstracta:

Decimos que una gramática es Ambigua cuando:

Dentro de las tareas que debe realizar un compilador, ¿A qué se refiere el análisis léxico?

Dentro de las tareas que debe realizar un compilador, ¿A qué se refiere el análisis semántico?

Dentro de las tareas que debe realizar un compilador, ¿A qué se refiere el análisis sintáctico?

El enunciado del teorema de síntesis es 'todo lenguaje aceptado por un autómata finito es regular'.

El lema del bombeo enuncia que para todo lenguaje regular infinito 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:

El lema de bombeo para lenguajes regulares se usa para…

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:

El teorema que indica que 'Si L es un lenguaje aceptado por un autómata finito M entonces existe una expresión regular γ tal que L = L(M) = L(γ)' se conoce como:

El teorema que indica que 'Si L es un lenguaje generado a partir de la expresión regular γ entonces existe un autómata finito M tal que L = L(γ) = L(M)' se conoce como:

En la descripción instantánea de un autómata a Pila: (q, w, L), ¿Qué significa la w?

En Teoría de la Computación lo importante es buscar la mejor manera de hacer las cosas, a esto se lo llama Computabilidad.

En un Autómata a 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

En un Autómata a Pila, cuando la cadena de entrada es aceptada por que ha sido leída por completo y se ha llegado a un estado final, sin importar el estado de la pila, decimos que la aceptación es:

En un Autómata a Pila, si desde el mismo estado, por 2 valores diferentes pasamos al mismo estado, estamos en presencia de:

En una máquina de Turing con cinta semi infinita

En una máquina de Turing la cinta es:

En una máquina de Turing multitareas:

En una máquina de Turing Universal es:

Expresión regular de todas las cadenas que tengan Σ={ a, b } y que empiecen con b.

Hablando de derivadas de expresiones regulares podemos afirmar que: 'El lenguaje representado por la derivada de una expresión regular…'

Hablando de propiedades de las expresiones regulares, si tenemos A.B ¿Qué debemos realizar con A y B? Solo 1 (una) opción es la correcta

Hablando de propiedades de las expresiones regulares, si tenemos la siguiente expresión A+B ¿A qué propiedad representa el signo +? Solo 1 (una) opción correcta.

Indicar cual es el autómata más sencillo (con menor capacidad de reconocimiento) que funcione de la siguiente manera. Dada cualquier cadena de x e y, sustituya todas las x's por las y's y devuelva una cadena con todas las y's al principio y las z's a continuación. Solo 1 (una) opción es correcta.

Kleene propuso dos teoremas principales que relacionan las expresiones regulares con los autómatas finitos. Selecciona 2 (dos) respuestas correctas.

La ambigüedad de una gramática surge cuando derivaciones diferentes generan estructuras diferentes para:

La clausura o clausura de Kleene se representa con:

La concatenación de 2 lenguajes independientes de contexto genera:

La ecuación característica del estado inicial es:

La expresión formal de un autómata a pila es: AP = (Σe, Q, Γ, q0, z0, f, F), donde Γ representa...

La expresión formal de una máquina de Turing es: MT = (Γ, Σ, b, Q, q0, f, F), ¿qué representa b?

La gramática tipo 2 se utilizan para: Solo 1 opción correcta

La máquina de Turing universal, ya que cuenta de los mismos componentes y conceptos para entender y resolver lo que le indicamos:

La Teoría de los Autómatas estudia las Maquinas Secuenciales

La Teoría de la Compatibilidad se interesa en:

La Teoría de la Complejidad Computacional es una parte de la Teoría de la Computación, a la que le interesa:

Las expresiones regulares se definen mediante:

Las gramáticas irrestrictas se relacionan con los siguientes tipos de lenguajes de la jerarquía de Chomsky:

Las gramáticas libres de contexto determinista se relacionan con los siguientes Lenguajes de acuerdo a la jerarquía de Chomsky:

Las gramáticas regulares se relacionan con los siguientes lenguajes de acuerdo a la Jerarquía de Chomsky:

Las gramáticas regulares se relacionan con los siguientes tipos de lenguajes de la jerarquía de Chomsky:

Las gramáticas libres de contexto se relacionan con los siguientes tipos de lenguajes de la jerarquía de Chomsky….

Las máquinas de Turing se diferencian de los autómatas a pila en que:

Las máquinas de Turing se relacionan con las siguientes gramáticas de acuerdo a la jerarquía de Chomsky:

Las operaciones con expresiones regulares tienen las siguientes propiedades: Seleccione las 4 (cuatro) respuestas correctas

Las operaciones que permiten definir expresiones regulares son:

Las transiciones que ejecuta un autómata a pila son variantes de las siguientes: Seleccione las 4 (cuatro) respuestas correctas.

Los autómatas a pila reconocen lenguajes Tipo 2 y solo esos.

Los autómatas a pila se relacionan con las siguientes gramáticas de acuerdo a la jerarquía de Chomsky:

Los autómatas a pila son herramientas que se usan para:

Los autómatas finitos se relacionan con las siguientes gramáticas de acuerdo a la jerarquía de Chomsky:

Los lenguajes aceptados por las máquinas de Turing son generados por gramáticas:

Los lenguajes de tipo 0 en la jerarquía de Chomsky se relacionan con los siguientes Lenguajes.

Los lenguajes de tipo 0 en la jerarquía de Chomsky se relacionan con los siguientes Tipos de máquina abstracta:

Los lenguajes de tipo 1 en la jerarquía de Chomsky se relacionan con los siguientes Lenguajes:

Los lenguajes de tipo 1 en la jerarquía de Chomsky se relacionan con los siguientes Tipos de maquina abstracta:

Los lenguajes de tipo 2 en la Jerarquía de Chomsky se relacionan con los siguientes Tipos de maquina abstracta:

Los lenguajes de tipo 3 en la jerarquía de Chomsky se relacionan con los siguientes Lenguajes.

Los lenguajes de tipo 3 en la jerarquía de Chomsky se relacionan con los siguientes Tipos de maquina abstracta:

Los lenguajes independientes del contexto correspondan a autómatas de pila y gramáticas independientes del contexto.

Los automatas de pila reconocen todos los lenguajes libres del contexto y sólo estos

Los ordenadores actuales están basados en el modelo de:

Los 'tokens' se pueden agrupar en dos categorías: cadenas específicas y cadenas no específicas. Indique ¿Cuál de las siguientes no es considerada una cadena especifica?

Luego de aplicar la operación Homomorfismo a un Lenguaje Regular, ¿Qué obtenemos? Solo 1 (una) opción correcta.

Marque los 4 (cuatro) aspectos de la Informática que han sido influencia por los científicos como Turing, con sus trabajos de investigación sobre los temas de estudio de esta materia:

Operaciones con expresiones regulares tienen las siguientes propiedades: seleccione las 4 (cuatro) respuestas correctas.

Para que podamos decir que un lenguaje es ambiguo

Partiendo de una gramática regular G es posible obtener la expresión formal de:

Pensando en el funcionamiento de la máquina de Turing, ¿Qué hace dicha maquina cuando lee esta transición: q1(0,X,D) partiendo del estado inicial q0?

Pensando en la ambigüedad de las gramáticas y lenguajes, podemos afirmar que:

¿Qué describe o expresa cada expresión regular (ER)?

¿Qué es un autómata?

¿Qué máquina abstracta es la que reconoce los lenguajes de tipo 1? Solo 1 (una) es la opción correcta.

¿Qué maquina abstracta se pueden utilizar en el análisis y diseño orientado a objetos? Solo 1 (una) respuesta correcta

¿Qué sucede con una máquina de Turing si se encuentra con el problema de la parada? Sólo una opción es la correcta.

Se puede demostrar que, dada una expresión regular existe un ......... capaz de reconocer el lenguaje que ésta define.

Sea el lenguaje L = { x^k y^k z^m: con k>0 y m par } ¿Cuál es la maquina más simple que puede reconocer este lenguaje?

Sea { L(G1) } el Lenguaje generado por gramática de tipo 1 y { L(G2) } el lenguaje generado por gramáticas de tipo 2, entonces { L(G1) incluido en L(G2) }

Sea L = {papa, mama}, ¿Cuál de las siguientes opciones representan la reflexión del mismo? Solo 1 (una) opción correcta

Sean los conjuntos A = {2,4,6,8} y B = {a,b,c}, indique cuál de las siguientes opciones es una relación sobre AXB.

Seleccione las 2 (dos) opciones correctas. ¿Cuáles de las siguientes afirmaciones son verdaderas en relación a las máquinas de Turing y sus características?

Seleccione las 2 (dos) opciones correctas. Los teoremas de Kleene que demuestran la equivalencia entre expresiones regulares y autómatas finitos son:

Seleccione las 3 (tres) opciones correctas. ¿Cuáles de las siguientes opciones se relacionan con características de una máquina de Turing?

Seleccione las 3 (tres) opciones correctas ¿Cuáles de los siguientes autómatas reconocen cadenas de un lenguaje regular?

Seleccione las 3 (tres) opciones correctas ¿Cuáles de los siguientes lenguajes se pueden asociar a algoritmos?

Seleccione las 4 (cuatro) opciones correctas. ¿Cuáles de las siguientes afirmaciones se relacionan con las máquinas de Turing y los lenguajes reconocidos?

Seleccione las 4 (cuatro) opciones correctas. ¿Cuáles de las siguientes afirmaciones son correctas en relación a los autómatas a pila, los lenguajes que reconocen y las gramáticas correspondientes?

Seleccione las 4 (cuatro) opciones correctas. Suponiendo la siguiente expresión regular: 1(01)*, ¿Cuáles de las siguientes expresiones representan el mismo lenguaje?

Seleccione las 4 (cuatro) opciones correctas. La expresión formal un autómata a pila incluye:

Seleccione cuatro de los campos en los que se aplica la Teoría de Autómatas

Seleccione 4 de los diferentes modelos de Máquina de Turing que pueden existir (cuatro correctas).

Seleccione las 4 (cuatro) opciones correctas. Dada la gramática G= ({a, b}, {S, A}, S, {S::=aS|aA, A::=bA|b},) si se realiza el proceso de transformar la gramática en el autómata finito que reconoce el lenguaje por ella generado, ¿Cuáles de los siguientes afirmaciones son correctas?

Si contamos con un lenguaje L, generado por una expresión regular y diseñamos un autómata finito que lo reconoce, siendo L = L (y) = L(M) Estamos frente a:

Si E y F son expresiones regulares, entonces E + F también lo es y se cumple L(E + F) = L(E) U L(F) :

Si hablamos de ambigüedad de las gramáticas, podemos decir que: 'Si una gramática es ambigua, posiblemente exista:'

Si L es un lenguaje regular su complemento también lo es:

Si L es un lenguaje regular sobre su alfabeto Σ, entonces también lo es su complemento:

Si la siguiente figura representa una transición de estados en una máquina de Turing genérica, la etiqueta sobre el arco significa que:

Si obtuvimos como resultado las cadenas de lenguaje L1 que no están en L2, siendo L1 y L2 regulares, ¿Qué operación de cierre les realizamos?

Si pasamos de un estado inicial, en un autómata a pila, directamente al estado de aceptación con la lectura de la cadena vacía. Podemos decir que este autómata a pila:

Si se simplifica la expresión regular a + a(b+aa)(baa)b + a(aa+b) se obtiene:

Si tenemos la secuencia X1 X2 … Xi 1 q Xi Xi+1… Xp, que representa la descripción instantánea de una Máquina de Turing, ¿Qué significa la letra q?

Si un lenguaje es aceptado por un Autómata de Pila No Determinista por estado final, entonces:

Si un problema no puede ser resuelto por una máquina de Turing, entonces:

Si un problema tiene una máquina que puede resolverlo entonces ese problema es:

Sobre las gramáticas del tipo 0 podemos afirmar que:

Suponiendo que la cadena de entrada de la siguiente máquina de Turing es 100011, ¿Cuál será la cadena resultado?

Suponiendo que se dispone de una máquina de Turing especificada mediante el diagrama de estados que se muestra, ¿cuál es el resultado de su operación?

Teniendo en cuenta las propiedades de cierre, podemos afirmar que: 'La reflexión de un lenguaje regular es'

Un arco del diagrama de estados de una máquina de Turing, los arcos que representan las transiciones se encuentran etiquetados con:

Un arco del diagrama de estados de un autómata a pila que conecta los estados p y q y está etiquetado con a,#/#a , significa que:

Un arco del diagrama de estados de un autómata a pila que conecta los estados p y q y está etiquetado con a,a/aa , significa que:

Un autómata a pila, debido a sus características cuenta con:

Un Autómata a Pila es Determinista si por:

Un autómata a pila puede aceptar una cadena por: Solo 2 (dos) respuestas correctas.

Un autómata a pila tiene la capacidad de:

Un autómata finito resuelve problemas de menor complejidad que un autómata linealmente acotado

Un compilador debe realizar las siguientes Tareas: Selecciona 4 (cuatro) respuestas correctas.

Un problema de decisión es decidible si:

Un proceso que puede resolverse mediante una máquina de Turing se conoce como:

Una máquina de Turing actúa como transductor cuando:

Una máquina de Turing es un modelo matemático consistente en un autómata que es capaz de implementar cualquier problema matemático expresado a través de un algoritmo.

La expresión formal de un autómata a pila es: AP = (Σe, Q, Γ, q0, z0, f, F), donde Σe representa...

Suponiendo el siguiente autómata finito: AF=({ 0, 1 }, { C0,C1,C2,C3,C4 }, CO, f, { C2,C4 }). El alfabeto de los símbolos terminales de gramática regular obtenida a partir de él es:

¿Cuál de las siguientes afirmaciones es verdadera en relación a las máquinas de Turing?