Lenguajes Formales y Computabilidad

La teoria de la complejidad computacional es una parte de la teoria de la computacion, a la que le interesa. Los recursos necesarios durante el calculo para resolver un problema. Cómo programar eficientemente sin considerar el uso de recursos. La estética y legibilidad del código fuente. El análisis de errores ortográficos en el software.

La teoria de la Computabilidad se interesa en: Optimizar el tiempo de ejecución de todos los algoritmos posibles. Diseñar interfaces gráficas atractivas para los programas. Hallar una solucion a un problema. Evaluar únicamente la complejidad espacial de los algoritmos.

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

Que maquina abstracta se puede utilizar en el analisis y diseño orientado a objetos?. Autómata finito determinista. Máquina de Von Neumann simple. Calculadora aritmética básica. Maquina de Turing.

Kleene propuso dos teoremas principales que relacionan las expresiones regulares con los automatas finitos: Seleccione las 2 (dos) Respuestas correctas. Teorema de Síntesis. Teorema de Análisis. Teorema de Complejidad. Teorema de Recursión. Teorema de Universalidad.

Las gramaticas regulares se relacionan con los siguientes lenguajes de acuerdo a la jerarquía Chomsky. Lenguajes recursivamente enumerables. Lenguajes sensibles al contexto. Lenguajes recursivos. Lenguajes libres de contexto.

Los lenguajes de tipo 0 en la jerarquía de Chomsky se relacionan con los siguientes tipos de maquina abstracta. Maquinas de Turing. Autómatas de pila. Autómatas lineales acotados. Autómatas finitos.

A las gramáticas de Tipo 3 le corresponden las: Máquinas de Turing universales. Autómatas lineales acotados. Autómatas de pila. Máquinas abstractas más simples.

De acuerdo a la jerarquía de Chomsky, los lenguajes regulares se relacionan con la siguiente maquina abstracta. Máquina de Turing. Autómata de Pila. Autómata Lineal Acotado. Autómatas Finitos.

A qué teorema pertenece la siguiente proposición? dado un autómata infinita es posible encontrar una expresión regular que denote el lenguaje representado por la autónoma. Teorema de Universalidad de Turing. Teorema de Complejidad de Chomsky. Teorema de Recursión de Kleene. En sentido inverso al teorema de sintaxis se expone el teorema de análisis o problema de análisis de klenee.

Sea L = {papa,mama}, Cual de las siguientes opciones representan la reflexion del mismo?. LR = {papa, papa}. LR={mama,papa}. LR = {mama, mama}. LR = {papa, mama, papa}.

Hablando de propiedades de expresiones regulares, si tenemos A.B, Que debemos realizar con A y B?. Aplicarles la negación. Interseccionarlos. Sumarlos. Concatenarlos.

Teniendo en cuenta las propiedades de cierre, podemos afirmar que, la reflexion de un lenguaje regular es. Contexto libre. Regular. Sensible al contexto. Tipo 0.

Cuando es util el lema de Bombeo de los lenguajes regulares?. Para simplificar expresiones regulares finitas. Únicamente para construir autómatas finitos equivalentes. Para todos los lenguajes, finitos e infinitos, con el fin de optimizar su representación. Este teorema solamente es util cuando al lenguaje que se aplica es infinito y es utilizado para demostrar que un lenguaje no es regular.

Que es un automata?. Un programa de computadora que ejecuta cálculos numéricos exclusivamente. Es un dispositivo abstracto teórico que recibe como entrada una cadena de estados y los procesa, cambiando de estado y generando una salida. Un diagrama de flujo físico usado para controlar máquinas industriales. Un conjunto de reglas gramaticales para escribir código en un lenguaje de programación.

Cual es el metodo que inserta un elemento en la pila de un Automata de Pila?. Push. Pop. Peek. Enqueue.

Un automata a Pila acepta una cadena por. Pila vacia. Longitud de la cadena. Número de transiciones realizadas. Estado de aceptacion.

Cual es la capacidad adicional que posee un Automata a Pila?. Capacidad de ejecutar múltiples hilos simultáneamente. Registro único para un solo símbolo. Una pila en la que se puede almacenar una cadena de simbolos. Memoria ilimitada para ejecutar cualquier programa.

Los Autómatas a Pila son herramientas que se usan para: Reconocer únicamente lenguajes regulares. Reconocer lenguajes generados por gramáticas libres de contexto. Ejecutar programas de manera secuencial sin cambios de estado. Diseñar interfaces gráficas de usuario.

En la descripción instantánea de un Autómata a Pila, (q,w,¿), Que significa la w?. W es lo que queda de la entrada, y que falta por analizar. La longitud total de la cadena de entrada. El número de transiciones realizadas hasta el momento. La pila completa del autómata.

Un Automata a Pila, debido a sus características cuenta 2 alfabetos: Uno del automata y el otro de la pila. Uno para los estados y otro para las transiciones. Uno para los autómatas finitos y otro para las máquinas de Turing. Uno para las salidas y otro para los errores.

En una máquina de Turing con cinta semi infinita. La cinta es infinita por la izquierda. La cinta tiene longitud fija y no puede crecer. La cinta es finita en ambas direcciones. La cinta es infinita por la derecha.

Cual de las siguientes afirmaciones acerca de la maquina de Turing es incorrecta?. La cabeza de lectura/escritura puede saltar a cualquier celda sin recorrer las intermedias. La cinta es infinita hacia derecha e izquierda, por lo tanto la afirmacion de que solo es infinita hacia la derecha es falsa. La máquina de Turing no puede simular algoritmos recursivos. Una máquina de Turing no puede mover su cabeza de lectura/escritura hacia la izquierda.

Cual de las siguientes no es modelo de maquina de Turing?. Máquina lineal acotada. Máquina multitape. Máquina universal. La maquina analitica.

Las maquinas de Turing se diferencian de los automatas a pila en que. Las maquinas de Turing la cabeza lectora puede retroceder. Las máquinas de Turing no pueden modificar la cinta. Las máquinas de Turing solo leen la entrada una vez. Las máquinas de Turing no tienen estados internos.

En la representacion de una maquina de Turing, que elementos no conforman su estructura?. Conjunto de estados. Función de transición. Alfabeto de entrada. La representacion de la maquina de Turing.

Cual de las siguientes afirmaciones acerca de una maquina de Turing es correcta?. Las máquinas de Turing solo pueden resolver problemas finitos. Se dice q todo problema computacionales pueden resolverse mediante una maquina de Turing, ya que estas maquinas son de mayor capacidad computacional. Las máquinas de Turing son menos poderosas que los autómatas a pila. Ningún problema computacional puede resolverse con máquinas de Turing.

Cuales de las cuatros opciones enumeran los componentes de una cinta de una Maquina de Turing Universal? seleccione las 4 correctas. Ejecucion de la maquina de Turing. Registro. Cinta de entrada. Memoria gráfica de doble buffer. Registro inicial.

Los ordenadores actuales estan basados en el modelo de. El autómata finito determinista. El autómata a pila. La máquina analítica de Babbage. La maquina de Turing Universal.

Cuando una maquina de Turing M, Reconoce un Lenguaje L?. Cuando M se detiene únicamente sobre las cadenas que no pertenecen al lenguaje L. Cuando M acepta una cadena si y solo si puede recorrer toda la cinta sin entrar en un ciclo infinito. Una maquina de Turing M, Reconoce un lenguaje L, si al analizar una cadena de entrada se para siempre, acepatndo la cadena y rechazando un caso contrario. Cuando M clasifica las cadenas según su longitud, aceptando las pares y rechazando las impares, independientemente de L.

Cuando un lenguaje es indecidible?. Se dice q un lenguaje es indecidible si no es un lenguaje recursivo. Cuando puede ser decidido únicamente por un autómata finito. Cuando existe un algoritmo que lo reconoce pero no uno que lo enumere. Cuando todas sus cadenas pertenecen al alfabeto vacío y no requiere análisis.

Cual de las siguientes proposiciones corresponde al teorema de Sintesis?. Si un autómata finito acepta un lenguaje infinito, entonces dicho lenguaje no puede representarse con expresiones regulares. Si dos autómatas finitos aceptan lenguajes distintos, entonces sus expresiones regulares asociadas deben ser necesariamente idénticas. Si L es un lenguaje generado a partir de la expresion regular y entonces existe un automata finito M tal que L = L(y) = L(M). Si un lenguaje es aceptado por una máquina de Turing, entonces puede expresarse siempre mediante una expresión regular equivalente.

Dada la siguiente gramatica G= ({S,A},{a,b,c},P,S) donde P contiene las siguientes producciones S→A, A→aAa, A→bAb, A→c ,que cadena de las siguientes no forma parte del lenguaje generado por G?. abbacabba. babacbaba. baacaab. abcba.

Las gramaticas irrestrictas se relacionan con los siguientes tipos de lenguajes de la jerarquia Chomsky. Tipo 1. Tipo 2. Tipo 0. Tipo 3.

Si pasamos de une estado inicial, en un automata a pila, directamente al estado de aceptacion con la lectura de la cadena vacia λ. Podemos decir que este automata a pila: Reconoce la cadena vacia. No reconoce ninguna cadena del lenguaje. Necesita consumir al menos un símbolo para poder aceptar. Solo reconoce cadenas de longitud mayor a 1.

Sea {L(G1)} el lenguaje generado por gramaticas de tipo 1 y {L(G2)} el lenguaje generado por gramaticas de tipo 2, entonces {L(G1)} c {L(G2)}. Falso. Verdadero.

Las operaciones con expresiones regulares tienen las siguientes propiedades, 4 correctas: La union es conmutativa. La concatenacion es distributiva respecto a la union. La union es asociativa. La concatenacion es asociativa. La concatenación es conmutativa.

Las transiciones que ejecuta un automata a pila son variantes de las siguientes, 4 correctas: Leer dos símbolos de la pila simultáneamente. Extraer un simbolo de la pila. Leer un simbolo de la pila. Leer un simbolo de la entrada. Insertar un simbolo de la pila.

Una máquina de Turing actúa como un traductor cuando: Modifica el acceso de la cinta realizando cierta función. Solo lee la cinta sin modificarla. Se mueve únicamente hacia la derecha. Se detiene sin producir ninguna salida.

El lema de bombeo enuncia que para todo lenguaje regular infinito L existe una constante m, dependiente de ese lenguaje, tal 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, con la condición adicional de que |z| ≥ m. El lema solo aplica si el lenguaje es finito. La cadena y puede tener longitud cero. w = xyz, |y| ≥ 1, |xy| ≤ m.

Dada la expresión formal de una gramática regular G = (∑N, ∑T, S, P), es posible obtener el autómata finito AFD = (∑T, 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 terminales. El alfabeto de los símbolos no terminales. Los símbolos iniciales y finales del lenguaje. Las producciones que generan la cadena vacía.

¿Cuál de las siguientes opciones se caracteriza por describir todas las cadenas aceptadas por un autómata dado?. Función de transición. Conjunto de estados inaccesibles. Tabla de movimientos del autómata. Ecuación característica.

Los lenguajes aceptados por los autómatas a pila son: Lenguajes regulares o tipo 3. Lenguajes recursivamente enumerables o tipo 0. Lenguajes sensibles al contexto o tipo 1. Lenguajes independientes del contexto o tipo 2.

Dada la expresión formal de una gramática regular G = (∑N, ∑T, S, P), es posible obtener el autómata finito AFD = (∑T, Q, f, q0, F) que reconoce el lenguaje generado por ella, donde ∑T, el conjunto de símbolos de entrada del autómata, se obtiene a partir de: El conjunto de símbolos no terminales. El conjunto de estados finales del autómata. El alfabeto de los símbolos de entrada. El conjunto de producciones de la gramática.

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: El autómata realiza una transición desde el estado p hasta el estado q con la entrada a independientemente del tope de la pila, luego de la transición desapila. El autómata apila el símbolo a en la pila después de leer a de la entrada. El autómata reemplaza el tope de la pila por a. El autómata realiza la transición sin consumir símbolo de entrada.

¿Cuál es el número mínimo de estados que debe tener una máquina de Turing para que acepte alguna cadena…?. Dos: estado inicial y estado de aceptación. Uno solo, porque una máquina de Turing puede aceptar sin necesitar estados adicionales. Cuatro como mínimo, debido a que siempre se requieren dos estados de procesamiento además de aceptación y rechazo. Tres: estado inicial, estado de rechazo y un único estado para procesar.

Sea el vocabulario (a, b) y la expresión regular a a* b b*. ¿Cuál es el lenguaje denotado…?. L = {aⁿ bᵐ con n ≥ 0 y m ≥ 0}. L = {aⁿ bᵐ con n > 1 y m > 1}. L = {aᵐ bⁿ con m > 0 y n > 0}. L = {aⁿ bᵐ con n > 0 y m > 0}.

¿Qué significa un arco del diagrama de estados de un autómata a pila que conecta los estados p y q y está etiquetado con “a, X/λ”?. El autómata cambia al estado q sin consumir entrada y apila un símbolo cualquiera. El autómata realiza una transición desde el estado p con una entrada a y, si el tope de la pila coincide con el símbolo indicado, lo desapila y pasa al estado q. El autómata realiza la transición solo si la pila está vacía. El autómata ignora por completo la entrada a y solo modifica la pila.

Partiendo de un autómata finito determinista puede obtenerse: La máquina de Turing linealmente acotada que replica paso a paso las transiciones del autómata determinista. El autómata a pila mínimo asociado, que permite reconocer extensiones infinitas del lenguaje original. La gramática sensible al contexto equivalente, obtenida aplicando reglas de expansión jerárquica sobre los estados del autómata. La gramática lineal por derecha que genera el lenguaje reconocido por el autómata.

Si para un autómata A sus ecuaciones características son: X₀ = a X₁, X₁ = b X₂ + a X₁ + b y X₂ + b + λ. Resolviendo X₁ se obtiene que: X₁ = a* b b*. X₁ = (ab)* a⁺ b*. X₁ = (a + b)* a b*. X₁ = a* (ba)* b.

¿Cuáles son los dos teoremas propuestos por Kleene que establecen la equivalencia entre las expresiones regulares y los autómatas finitos?. Teorema de síntesis. Teorema de análisis. Teorema de clausura y teorema de expansión. Teorema de conversión directa y teorema de minimización. Teorema de correspondencia sintáctica y teorema de derivación estructura.

¿Cuál de las siguientes afirmaciones es verdadera en relación al lema de bombeo?. El lema de bombeo se usa para demostrar que un lenguaje no es regular. El lema de bombeo se utiliza para construir autómatas a pila. El lema de bombeo garantiza que todo lenguaje regular puede generar cadenas infinitas. El lema de bombeo se aplica solo a lenguajes finitos.

La información almacenada durante la ejecución de un autómata a pila se recupera siguiendo el principio: FIFO. Basado en prioridad del símbolo más pequeño. LIFO. Orden aleatorio sin restricción.

Toda máquina de Turing posee: Una serie de estados conectados sin cinta ni cabezal, que procesa las cadenas únicamente mediante transiciones de estado. Una memoria limitada a un número fijo de celdas y un cabezal que únicamente puede escribir, sin posibilidad de leer los símbolos existentes. Una cinta infinita dividida en celdas y un cabezal de lectura/escritura que puede moverse en ambas direcciones sobre ella. Una cinta finita y un cabezal de lectura/escritura que solo puede moverse hacia la derecha, deteniendo el procesamiento al llegar al final.

El problema de la parada o el problema de la detención para máquinas de Turing es un: Problema indecidible. Problema de complejidad lineal. Problema resoluble mediante autómata finito. Problema decidible.

Un lenguaje se dice inherentemente ambiguo si: Siempre puede generarse con una gramática regular. No existe una gramática no ambigua que lo genere. Solo puede generarse mediante un autómata finito determinista. Es generado necesariamente por una gramática tipo 3.

Si para un autómata A sus ecuaciones características son: X₀ = a X₁, X₁ = b X₂ + a X₁ + b y X₂ = b X₂ + b + λ. Resolviendo X₂ se obtiene que: X₂ = b*. X₂ = λ. X₂ = b⁺. X₂ = a*.

Si para un autómata A sus ecuaciones características son: X₀ = a X₁, X₁ = b X₂ + a X₁ + b y X₂ = b X₂ + b + λ. Resolviendo X₀ se obtiene que: X₀ = a* b b* a. X₀ = a b* a* b. X₀ = a a* b b*. X₀ = a (a + b)* b*.

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: Q = {A, B, C, F}. Q = {A, B, C, F, G}. Q = {A, B, C, D, F}. Q = {A, B, C}.

¿Cuál es el tipo de autómata capaz de reconocer el lenguaje L = { xⁿ yᵐ | n > 1 }?. Un autómata a pila. Autómata finito determinista. Autómata finito no determinista. Máquina de Turing linealmente acotada.

Si es un autómata finito, q₀ es el estado inicial, ¿qué se obtiene resolviendo su ecuación característica X₀?. El lenguaje no regular generado por la entrada del autómata. El autómata a pila asociado. La gramática libre de contexto equivalente. El lenguaje regular aceptado por el autómata finito.

El lenguaje aceptado por un autómata a pila puede ser caracterizado como: Lenguaje aceptado por transición determinista únicamente. Lenguaje aceptado por vaciado de pila. Lenguaje aceptado por estado final. Lenguaje aceptado por coincidencia exacta con una cadena de referencia.

¿Cuál de las siguientes es una característica de los autómatas finitos?. Pueden resolver problemas indecidibles. Pueden almacenar memoria ilimitada en una pila. Reconocen cualquier lenguaje libre de contexto. Solo reconocen lenguajes regulares.

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

¿Cuáles de las siguientes opciones se relacionan con características de una máquina de Turing?. En cada instante la máquina puede leer un solo dato de la secuencia. La máquina de Turing posee memoria ilimitada en varias pilas independientes para cada símbolo de la cinta. Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. La máquina de Turing puede mover el cabezal diagonalmente sobre la cinta y leer varios símbolos a la vez. El cabezal puede moverse a derecha (R) o a izquierda (L) y leer el contenido de una celda o escribir en ella.

Las transiciones en un autómata a pila dependen de: Solo del estado actual. El estado actual, del símbolo de entrada y del símbolo en el tope de pila. Únicamente del símbolo de entrada. Del estado actual y la longitud de la pila.

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: ∑ = {0, 1, #, λ}. ∑ = {0, 1, a, b}. ∑ = {0, 1, #}. ∑ = {0, 1}.

¿Cuál es el lenguaje denotado por la siguiente expresión regular 0*10?. L = {0ⁿ 1 0ᵐ con n y m ≥ 0}. L = {0ⁿ 10ⁿ con n ≥ 1}. L = {1 0ⁿ con n ≥ 0}. L = {0ⁿ 1 con n ≥ 0}.

La expresión formal de una máquina de Turing, donde Γ representa: El alfabeto de entrada del autómata. El conjunto de transiciones posibles. El conjunto de estados de la máquina. El alfabeto de los símbolos de la cinta.

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: El alfabeto de los símbolos de entrada. El conjunto de símbolos no terminales. El conjunto de producciones de la gramática. El alfabeto de los símbolos de entrada. El conjunto de estados finales del autómata.

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. Falso. Verdadero.

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

¿Cuál de los siguientes autómatas puede reconocer el lenguaje L = {0ⁿ 1 2ᵐ 0ᵐ | m, n > 0}?. Autómata finito determinista. Autómata finito no determinista. Máquina de Turing con cinta finita. Un autómata a pila.

¿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?. (a + b)* ab (a + b)*. (a + b)* ba (a + b)*. b* a* b* a*. a* b* a* b*.

¿Cuál de las siguientes afirmaciones es correcta en referencia a la precedencia de operadores en una expresión regular?. La concatenación tiene mayor precedencia que el asterisco. Los paréntesis tienen menor precedencia que la concatenación. La unión tiene la mayor precedencia. El asterisco de la cerradura tiene la mayor precedencia.

¿Cuál de las siguientes afirmaciones es correcta?. Una máquina de Turing reconoce un lenguaje L si puede escribir símbolos adicionales en la cinta sin importar si la cadena pertenece a L o no. 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 detiene solo algunas cadenas de L y otras cadenas se rechazan sin detenerse. Una máquina de Turing reconoce un lenguaje L si, para cualquier entrada, puede moverse infinitamente por la cinta sin llegar a un estado final.

En una máquina de Turing, la función de transición de estados se representa como: f: Q × Γ → Q × Γ. f: Q × Σ → Q × Σ × {R, L}. f: Q × Γ → Q × Γ × (I, D, P). f: Q × Γ × Σ → Q × Γ.

A diferencia de los autómatas finitos, los autómatas a pila cuentan con: Una capacidad ilimitada de estados sin pila. La habilidad de moverse diagonalmente sobre la entrada. La capacidad de leer múltiples símbolos a la vez. Una memoria auxiliar.

¿Qué funciones están definidas por las siguientes reglas? A := 0B, B := 1C, B := 1, C := 0B, A := λ Funciones: f(A,0) = B. f(B,1) = F. f(A,λ) = F. f(B,1) = C. f(C,0) = B.

A las gramáticas del Tipo 3 le corresponde: Las máquinas abstractas más simples. Lenguajes que requieren memoria ilimitada para ser reconocidos. Lenguajes que solo pueden aceptarse con máquinas de Turing. Lenguajes dependientes del contexto o tipo 1.

¿A qué teorema corresponde la siguiente 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 análisis se establece el teorema de minimización de estados, que indica cómo reducir el número de estados de un autómata sin cambiar el lenguaje reconocido. Según el teorema de correspondencia sintáctica, toda gramática regular puede transformarse en un autómata a pila que genere el mismo lenguaje. 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 dicho autómata. El teorema de expansión estructural afirma que cualquier autómata finito puede convertirse en una máquina de Turing con una memoria adicional ilimitada, preservando el lenguaje.

¿A qué teorema pertenece la siguiente proposición? "Dado un autómata infinito es posible encontrar una expresión regular que denote el lenguaje representado por la autónoma.". El teorema de correspondencia estructural indica que todo autómata infinito puede ser representado por una gramática libre de contexto equivalente. En sentido inverso al teorema de sintaxis se expone el teorema de análisis o problema de análisis de Kleene. Según el teorema de minimización, cualquier autómata infinito puede reducirse a un número mínimo de estados manteniendo la misma expresión regular. En sentido inverso al teorema de conversión directa, se establece el teorema de expansión de estados, que permite transformar un autómata infinito en un autómata finito sin cambiar su lenguaje.

¿Cómo influye el problema de la parada de Turing en la inteligencia artificial?. Obliga a que todos los algoritmos de IA usen únicamente autómatas finitos. Asegura que todos los sistemas inteligentes pueden predecir el futuro correctamente. Permite garantizar que todos los programas de IA siempre se detendrán. Imposibilita saber si los programas inteligentes funcionarán 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. Falso. Verdadero.

¿Con qué tipo de problema puede clasificarse la conjetura de Collatz?. Problema de complejidad lineal. Indecidible. Resuelto por autómatas finitos. Decidible.

¿Cuál de estas opciones es una característica de los autómatas finitos?. Pueden contar un número ilimitado de símbolos usando la pila. Tienen memoria infinita y pueden reconocer cualquier lenguaje. Pueden retroceder y modificar símbolos de la entrada arbitrariamente. Tienen memoria finita y no pueden contar de forma ilimitada.

¿Cuáles de las cuatro opciones enumeran los componentes de la cinta de una Máquina de Turing Universal? Seleccione 4 respuestas correctas: Registro. Cinta de entrada. Unidad de control de errores. Ejecución de la máquina de Turing. Registro inicial.

¿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. Las máquinas de Turing no pueden reconocer ningún lenguaje que un autómata finito pueda. Una máquina de Turing tiene memoria limitada y no puede simular algoritmos arbitrarios. Toda máquina de Turing puede resolver problemas indecidibles sin limitaciones.

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?. Autómata finito no determinista. Máquina de Turing linealmente acotada. Un autómata a pila. Autómata finito determinista.

¿Cuál de las siguientes afirmaciones es correcta en cuanto a una máquina de Turing universal?. Una máquina de Turing universal solo puede ejecutar autómatas finitos. 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 puede procesar cadenas de longitud arbitraria. Una máquina de Turing universal está limitada a problemas decidibles únicamente.

¿Cuál de las siguientes afirmaciones es verdadera?. La intersección de dos lenguajes regulares genera un lenguaje de tipo 2. L = L1 ∩ L2 solo será regular si L1 y L2 son gramáticas independientes del contexto. Si L1 y L2 son lenguajes regulares definidos sobre un mismo alfabeto, entonces L = L1 ∩ L2 también lo es. Si L1 y L2 son regulares, entonces L1 ∩ L2 siempre es no regular.

Dos expresiones regulares a y B son equivalentes (a = B) si: El lenguaje que describen es el mismo: si L(a) = L(B). Son equivalentes si tienen la misma longitud de cadena más larga. Son equivalentes si a y B provienen de la misma gramática sin importar el lenguaje generado. Son equivalentes si utilizan los mismos símbolos en la expresión, aunque describan lenguajes distintos.

¿Cuál de las siguientes afirmaciones es verdadera en relación a los lenguajes aceptados por los autómatas finitos?. Las expresiones regulares de los lenguajes aceptados por los autómatas finitos son fácilmente descritas por expresiones simples llamadas expresiones regulares. 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 regulares. Los lenguajes aceptados por autómatas finitos requieren siempre memoria ilimitada para ser descritos. Las expresiones regulares de los lenguajes aceptados por autómatas finitos no pueden representarse de manera finita.

¿Cuál de las siguientes no es modelo de máquina de Turing?. La máquina de Turing linealmente acotada. La máquina de Turing universal. La máquina de Turing no determinista. La máquina analítica.

¿Cuáles de las tres opciones corresponden a máquinas abstractas que resuelven problemas computables? Seleccione 3 respuestas correctas: Gramáticas libres de contexto. Autómatas Linealmente Acotados. Autómatas a pila. Máquina de Turing. Autómatas finitos no deterministas.

¿Cuál de las siguientes proposiciones corresponde al Teorema de Síntesis?. Si L es un lenguaje generado por un autómata finito, entonces no es posible construir una expresión regular que lo describa. 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). Todo lenguaje generado por una gramática libre de contexto puede ser representado únicamente por un autómata a pila, sin expresión regular equivalente. Si L es un lenguaje recursivamente enumerable, entonces siempre existe un autómata finito que lo reconoce y una expresión regular que lo denota.

Una expresión es regular si: Solo puede ser generada por una gramática tipo 1. Requiere una máquina de Turing para ser aceptada. Es reconocida por un autómata de estado finito. Es reconocida únicamente por un autómata a pila.

¿Cuál de los siguientes autómatas puede reconocer el lenguaje L = {0ⁿ 1 2ᵐ 0ᵐ | m, n > 0}?. Autómata finito determinista. Autómata finito no determinista. Un autómata a pila. Máquina de Turing con cinta finita.