Preguntas correctas PDF

Preview

Summary

Preguntas con respuestas correctas...

Description

¿Cuál de los siguientes enunciados relativos al lenguaje xnynzn siendo n un entero positivo, es cierto? Es posible construir una máquina de Turing que acepte dicho lenguaje Con relación a los analizadores sintácticos tipo LL(k): Un analizador sintáctico LL(k) reconoce el lenguaje generado por una gramática independiente del contexto haciendo uso del principio de preanálisis. En la construcción de un analizador sintáctico tipo LL(k), si la cima de la pila es un no terminal: Se sustituye por el valor que indica la celda correspondiente al símbolo (o símbolos) de preanálisis en la tabla del analizador. Sea el lenguaje definido por L={xmynzp; siendo m,n,p ≥0 y p=m+n} y sean L(G1), L(G2) y L(G3) los lenguajes generados por cada una de las gramáticas indicadas en la figura.

L=L(G2) Sea L el lenguaje que reconoce el autómata finito de la figura y las gramáticas G1, G2 y G3 en las que S es el axioma. Elegir la respuesta correcta.

La gramática G2 genera L. El lenguaje generado por gramática: {S→SS/xy/yx}: Es un lenguaje regular. Relativo a la complejidad: La complejidad temporal en una máquina de Turing M es igual al nú mero de pasos que ejecuta M antes de pararse. La siguiente gramática, donde S es el axioma.

La gramática genera el lenguaje representado por la expresión regular 0*1 (0 + 1)*

Dado el lenguaje L={xnyn ; n≥0}, el lema del bombeo para lenguajes regulares permite demostrar que: No es posible construir un autómata finito que reconozca L. Para el AFND-λ de la figura:

(t, b) = {q, s, t} Sean los lenguajes L1 = {0n1m0n / n, m>0} y L2 = {0n1n / n >1} y sea L el lenguaje que reconoce (por vaciado de pila) el autómata de la figura.

L = L2

Se trata de determinar la expresión regular del autómata finito de la figura a partir del aná lisis de Kleene:

La expresion regular es: r=a*[b(a+b)*b+a] Para las gramáticas de la figura:

Las gramáticas G1 y G2 son equivalentes. Para el autómata finito de la figura:

Todas las respuestas son ciertas. Escoger la respuesta correcta: La regla A:=AB1C es del tipo independiente del contexto. Siendo Q el conjunto de estados, Σ el alfabeto de entrada y Δ el alfabeto de salida : La función de salida de una máquina de Mealy es: :Q×Σ→Δ

Queremos dibujar el diagrama de transiciones correspondiente a la concatenación del lenguaje aceptado por M1 seguido por el lenguaje aceptado por M2,

De entre las siguientes soluciones elegir la correcta.

El diagrama planteado en la figura 1 es correcto.

Para la máquina de Turing de la figura.

La máquina solo acepta las palabras en {a,b} que terminan con una a. Sea L el lenguaje de los números múltiplos de 3 definidos en el alfabeto Σ={0,1,2} (el cero se considera múltiplo de 3) y sean los autómatas finitos de la figura:

El AFD1 reconoce dicho lenguaje. Dada la expresión regular b*a+(ba+)*bb, decir cuál de las siguientes cadenas pertenece al lenguaje que denota: baabb El algoritmo genérico de un analizador léxico: Requiere especificar el estado inicial.

Queremos transformar la máquina de Mealy de la figura en una máquina de Moore. Elegir la respuesta correcta:

La máquina de Moore 1 es equivalente a la máquina de Mealy del enunciado. Sea el AFD dado por la siguiente tabla, el autómata mínimo equivalente tiene el siguiente nú mero de estados:

La respuesta correcta es: 3

La figura representa una máquina de Turing de tres pistas para sumar dos números binarios. Suponiendo que los dos sumandos tienen la misma longitud y que la cabeza de lectura/escritura está inicialmente en el extremo izquierdo de los mismos:

Las transiciones c3 y c4 corresponden a las expresiones: c3=(1,1,B), (1,1,1), L y c4=(B,B,B), (B,B,1), S. Proponemos la tabla de la figura para construir un analizador sintáctico LL(k) con k mínimo, para el lenguaje con axioma A y las siguientes reglas de producción:

La regla a aplicar en la celda que está en blanco es x.

Para el autómata de pila de la figura:

Todas las respuestas son ciertas. Se trata de simular un diferenciador digital que actúe generando un tren de pulsos de valor "1" cuando la señal cambia y "0" cuando la señal permanece constante. Por ejemplo, para una entrada: "0011100" la salida sería: "0010010". Elegir la respuesta correcta para las dos máquinas secuenciales MO y ME de la figura.

La máquina MO simula la respuesta del diferenciador digital. (Obviando el primer valor de salida) Sean ∑T = {0,1,2}, ∑N = {A, B, C, D}, A el axioma y la regla 1B1A:=1B11B1, pertenece, como más restrictiva, a una gramática del tipo: dependiente del contexto

Para el autómata finito de la figura:

Las tres respuestas son falsas. Sea el AFND-λ dado por la siguiente tabla, donde las casillas en blanco indican el conjunto vacío, entonces la λ-clausura del estado v es:

q, r, s, u, v Sea L el lenguaje del alfabeto {0, 1} formado por las cadenas que acaban en 00. Indique cuál de las siguientes autómatas acepta dicho lenguaje.

Dada la expresión regular a+ decir en cuál de los siguientes autómatas el lenguaje aceptado no coincide con el que ella denota:

M2 Indique cuál de las afirmaciones siguientes es verdadera: Todo autómata determinista definido para un alfabeto con n símbolos debe contener al menos n transiciones. Dada la expresión regular (0+2)*1+ decir cuál de los siguientes autómatas el lenguaje aceptado coincide con el que ella denota:

M2 Dada la tabla del autómata, los estados A y B son equivalentes porque:

Los dos tiene las mismas transiciones y los dos son no finales

Dado el autómata de la figura, decir cuál de las expresiones regulares siguientes denota el lenguaje que acepta este autómata:

xy*x+yx*y+xy*+yx* Sea la gramática G = (∑T,∑N,S,P), siendo ∑T = {0, 1, 2}, ∑N = {A, B}, S = A y P = {A -> 0B/2, B -> 0A/1}, decir cuál de las siguientes cadenas pertenece al lenguaje generado por dicha gramá tica: 0001 Dada la expresión regular (a+bb)*, decir cuál de las siguientes cadenas pertenece al lenguaje que denota: abbbbabb Dado el autómata de la figura, decir cuál de las expresiones regulares siguientes denota el lenguaje que acepta este autómata:

(1+01*0)*

Para los autómatas A1, A2 y A3 de la figura, elegir la respuesta correcta.

La tabla no es correcta. Sea L el lenguaje del alfabeto {0, 1} formado por las cadenas no vacías que no tienen ceros consecutivos. Sean M1 y M2 los autómatas de la figura:

L=L(M1)...