Lenguajes Formales p2

Cuales de las siguientes afirmaciones son correctas como definición de equivalencias entre dos máquinas de turing?? 4 correctas. Dos máquinas de Turing son equivalentes si una no para para alguna entrada, la otra tampoco lo hace. Dos máquinas de Turing son equivalentes si ambas aceptan y/o reconocen las mismas palabras. Dos máquinas de Turing son equivalentes si ambas realizan la misma acción sobre sus entradas. Dos máquinas de Turing son equivalentes si para cada entrada posible, los contenidos de la cinta al final del proceso son iguales. Dos máquinas de Turing son equivalentes si ambas realizan la misma acción sobre algunas de sus entradas. Dos máquinas de Turing son equivalentes si ambas realizan la misma acción sobre sus salidas.

El número de ecuaciones características de un autómata finito depende de: El número de estados del autómata. El número de salidas del autómata. El número de entradas del autómata. El número de símbolos del autómata.

El enunciado del teorema de análisis de Klene es: Todo lenguaje regular es aceptado por un autómata finito. Todo lenguaje aceptado por un autómata finito es regular. Todo lenguaje es aceptado por un autómata finito. Toda gramática es aceptada por un autómata finito.

El conjunto de producciones de la gramática. El axioma S de la gramática regular. El conjunto de estados. Las funciones de transición.

Los autómatas a Pila y los AF aceptan los mismos lenguajes. Verdadero. Falso.

Si un autómata finito, q0 es el estado inicial. Que se obtiene resolviendo su ecuación característica x0?. El lenguaje regular aceptado por el autómata finito. La gramática regular. La minimización del autómata. El árbol de derivación.

Una máquina de Turing actúa como un traductor cuando: Modifica el acceso de la cinta realizando cierta función. Modifica el ingreso de la cinta. Valida la información de la cinta. Realizando solo modificación de símbolos.

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: w = xyz, |y| ⪴ 1, |xy| ⪴ m. w = x, |y| ⪴ 1, |xy| ⪴ m. w = xy |y| ⪴ ', |xy| ⪴ m. w = y |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 = (∑, 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 producciones definidas. El axioma.

¿Cuál de las siguientes opciones se caracteriza por describir todas las cadenas…dado en un autómata dado?. Ecuación característica. Reglas de producción. Cadenas del alfabeto. Árbol de derivación.

Los lenguajes aceptados por los autómatas a pila son: Lenguajes independientes del contexto o tipo 2. Lenguajes dependientes del contexto o tipo 1. Lenguajes regulares o tipo 3. Lenguajes sin restricciones o tipo 0.

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: El alfabeto de los símbolos de entrada. El alfabeto de los símbolos de salida. Las producciones.

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 e independientemente del tope de la pila, luego de la transición desapila. El autómata realiza una transición desde el estado p hasta el estado q con la entrada y validando que simbolo tiene el tope de la pila, luego de la transición desapila. El autómata realiza una transición desde el estado p hasta el estado q con la entrada a.

¿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, estado inicial. Uno, estado de aceptación. Tres, estado inicial, un estado intermedio y el estado de aceptación.

Sea el vocabulario (a, b) y la expresión regular aa*bb*, ¿Cuál es el lenguaje denotado …?. L = {an bm con n>0 y m>0}. L = {an bm con n>1 y m>1}. L = {am bam con n>0 y m>0}. L = {am bm con n>1 y m>1}.

Un arco del diagrama de estados de un autómata a pila, que conecta… significa que: El autómata realiza una transición desde el estado p con una entrada a y…. El autómata realiza un cambio de estado. El autómata realiza modificación en la pila.

Partiendo de un autómata finito determinista puede obtenerse: La gramática lineal por derecha que genera el lenguaje reconocido por el autómata. La gramática lineal por izquierda que genera el lenguaje reconocido por el autómata. La gramática lineal que genera el lenguaje reconocido por el autómata.

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: X1 = a*bb*. X1 = a*bba*. X1 = a*baba*. X1 = a*bbaa*.

Los teoremas de Kleene que demuestran…regulares y autómatas finitos son: Teorema de análisis y Teorema de síntesis. Teorema de bomeo. Teorema de lenguaje regular.

¿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 usa para demostrar que un lenguaje es regular. El lema de bombeo se usa para gramáticas regulares. El lema de bombeo se usa para demostrar que un lenguaje tiene expresiones repetitivas.

La información almacenada durante la ejecución de un autómata a Pila…. LIFO. FIFO.

Toda máquina de Turing posee: Una cinta infinita dividida en celdas y un cabezal de lectura/escritura que puede moverse en ambas direcciones sobre ella. Dos cintas infinitas divididas en celdas y un cabezal de lectura/escritura. Un cabezal de lectura/escritura que puede moverse en ambas direcciones sobre ella. Una cinta finita y un cabezal.

El problema de la parada o el problema de la detención para máquinas de Turing es un: Problema indecidible. Problema decidible. Problema con resolución.

Un lenguaje se dice inherentemente ambiguo si: No existe una gramática no ambigua que lo genere. Existe una gramática no ambigua que lo genere. Existe una gramática ambigua que lo genere.

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: X2 = b*. X2 = ba*. X2 = baab*.

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 }. {0,1}. P = ((A:=0B), (A:= λ), (B:=1C), (B:=1), (C:=0B). A.

¿Cuál es el tipo de autómata capaz de reconocer el lenguaje L = { xⁿym|n>1}?. Un autómata a pila. Un ALA. Una MT. Mealy. Moore.

El lenguaje aceptado por un autómata a pila puede ser caracterizado como: Lenguaje aceptado por vaciado de pila. Lenguaje aceptado por estado final. Lenguaje aceptado por AP. Lenguaje aceptado Vaciado de pilaa.

¿Cuál de las siguientes es una característica de los autómatas finitos?. Solo reconocen lenguajes regulares. Solo reconocen lenguajes tipo 1. Solo reconocen lenguajes tipo 2. Solo reconocen lenguajes tipo 0.

¿Cuál de las siguientes es una característica de los autómatas finitos?. Solo reconocen lenguajes regulares. Solo reconocen lenguajes tipo 0. Solo reconocen lenguajes tipo 2. Solo reconocen lenguajes tipo 1.

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

¿Cuáles de las siguientes opciones se relacionan con características de una máquina de Turing?. El cabezal puede moverse a derecha (R) a izquierda (L) y leer el contenido de una celda o escribir en ella. En cada instante la máquina puede leer un solo dato de la secuencia. Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. Una máquina de Turing es un autómata que se mueve sobre una cinta de datos.

Las transiciones en un autómata a pila dependen de: El estado actual, del símbolo de entrada y del símbolo en el tope de pila. El estado final y del símbolo en el tope de pila. El estado actual y del símbolo en el tope de 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}.

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

La expresión formal de una máquina de Turing, donde Γ representa: El alfabeto de los símbolos de la cinta. El alfabeto de los símbolos de entrada. El alfabeto de los símbolos de salida.

Dado 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 alfabeto de los símbolos de salida. El alfabeto de los símbolos terminales.

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

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

¿Cuál de los siguientes autómatas puede reconocer el lenguaje L = {0n12m0m | m, n > 0}. Un autómata a pila. Un ALA. Una MT.

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

¿Cuál de las siguientes afirmaciones es correcta en referencia a la precedencia de operadores en una expresión regular?. El asterisco de la cerradura tiene la mayor precedencia. El operador (+). El operador (.).

¿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 siempre para. Una máquina de Turing no 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 siempre para, y lo hace en un estado inicial.

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

A diferencia de los autómatas finitos, los autómatas a pila cuentan con: Una memoria auxiliar. Una memoria extra. Una cinta.

Cual es el calculo que realiza la maquina de Turing que se muestra en la siguiente imagen?. Calcula el doble de un número expresado en binario. Calcula el triple de un número expresado en binario. Calcula un número expresado en binario.

Cual es el calculo que realiza la maquina de Turing que se muestra en la siguiente imagen?. Idéntica a la cadena de entrada. Diferente a la cadena de entrada.

Para el autómata cuyo diagrama de estados se presenta en la siguiente imagen, las ecuaciones características son: x0= ax1 x1= bx2 + ax1 + b x2= bX2 + b + λ. x0= ax x1= bx + ax + b x2= bX2 + b + λ. x0= ax x1= bx2 + ax2 + b x2= bX2 + b + λ. x0= ax2 x1= bx + ax + b x2= bX2 + b + λ.

Seleccione las 4 (cuatro) operaciones correctas. ¿Cuáles de las siguientes afirmaciones se reconoce en una máquina de Turing y los lenguajes reconocidos?. Una MT Reconoce lenguajes de tipo 0. Todo procedimiento computacional puede ser realizado por una MT. Si un problema no puede ser resuelto con MT entonces no tiene solución. Los lenguajes de tipo 0 describen todo problema que puede ser resuelto por una computadora. MT posee memoria extra como AP.

Que cadena forma esta MT ?. 10100. 10110. 10010. 10101.

La expresión regular del lenguaje aceptado por el autómata, cuyo diagrama se muestra en la siguiente imagen. V + WX*Y. V + WXY*. V + XWX*Y. V + WX*YY.

f(A,0) = B, f(A, λ) = F, f(B, 1) = C, f(B,1) =F, f(C, 0) = B donde F es estado final. f(A,0) = B, f(A, λ) = F, f(B, 1) = C, f(B,1) =F, f(C, 0) = B donde C es estado final. f(A,0) = B, f(A, λ) = F, f(B, 1) = C, f(B,1) =F, f(C, 0) = B donde A es estado final. f(A,0) = B, f(A, λ) = F, f(B, 1) = C, f(B,1) =F, f(C, 0) = B donde B es estado final.

Suponiendo la gramática regular… la función de transición del autómata obtenido a partir de ella es: A. B. C.

Cual es el lenguaje aceptado por el automata a pila cuyo diagrama de estados se muestra en las siguiente imagen. L= {a^n b^n con n>=0}. L= {a^n b^n con n>=1}. L= {a^n b^n con n<=0}.

A que tipo de automata correspodne la talba de transición de estados que se muestra en la siguiente imagen?. MT. ALA. AF.

Cual es una posible expresión regular que expresa el lenguaje aceptado por el siguiente automata?. (ab)*a. (a*b*)a. (a*b)a*. (ab)a*.

Dada la siguiente imagen identifique las acciones que se realizan sobre la pila: En la transición entre q0 y q1 con una entrada a y tope de la pila x ese tope se desapila. En la transición entre q0 y q1 con una entrada b y tope de la pila x ese tope se desapila. En la transición con una entrada a y tope de la pila x ese tope se desapila.

x0 =bx0+ax1+a x1=bx1+ax0+b+λ. x0 =bx0+ax1+a x1=bx+ax+b+λ. x0 =bx+ax1+a x1=bx1+ax+b+λ.

Suponiendo que la cadena de entrada de la siguiente maquina de Turing es 100011. ¿Cuál ser ala cadena resultado?. 1100111. 1100011. 1111001. 1100110.

El siguiente diagrama de estados representa una máquina de Turing ¿Cuál es el resultado de la operación de la máquina si el alfabeto de entrada es {0,1} ?. La máquina de Turing calcula el complemento A2 de un número de notación binaria. La máquina de Turing calcula el suplemento A2 de un número de notación binaria. La máquina de Turing calcula el complemento A2 de un número.

Cual es el lenguaje aceptado?. El lenguaje aceptado es L=(0n1n n>0). El lenguaje aceptado es L=(0n1n n>1). El lenguaje aceptado es L=(10n1n n>0). El lenguaje aceptado es L=(01n1n n>0).

Que retorna esta MT ?. Calcula el sucesor de un número expresado en binario. Calcula el anterior número expresado en binario.

¿Cuál es el cálculo que realiza la máquina de Turing que se muestra en la siguiente imagen?. Calcula el sucesor de un número expresado en binario. Calcula el anterior número expresado en binario.

¿Cuál es el resultado de la operación de la siguiente máquina de Turing?. Transforma la cadena de entrada reemplazando la subcadena "ba" por "ab". Transforma la cadena de entrada reemplazando la subcadena "ab" por "ba". Transforma la cadena de entrada reemplazando la subcadena "baa" por "aab".

¿Cuál es la expresión regular del lenguaje reconocido por el autómata?. b*(ab*ab*a)*. b*(ab*ab*). b(ab*ab*)*. b*(abab*)*.

¿Cuál es una expresión regular correcta para el lenguaje reconocido por el autómata cuyo diagrama se muestra en la siguiente imagen?. (ab)*a. (a*b)*a. (ab)*ba. (aab)*a.

¿Cuál es una expresión regular correcta para el lenguaje reconocido por el autómata cuyo diagrama se muestra en la siguiente imagen?. a ^nb^n / n ≥ 0. a ^nb^n / n ≥ 1. a ^nb / n ≥ 0.