Test_FinalExamQuestions

español e ingles

a, c

Marque las afirmaciones verdaderas(mas de una):

a. Si Σ={a, b, c} entonces Σ0= λ.

b. Σ={a, b, λ} es un alfabeto.

c. Si Σ={a, b, c}, entonces {a, b, c} puede ser un lenguaje sobre Σ.

d. Si Σ={a, b, c}, entonces Ø no es un lenguaje sobre Σ.

b, d

Marque las afirmaciones verdaderas(mas de una):

a. ABC::=AB es una regla de una gramática de tipo 1, sensible al contexto.

b. Toda gramática regular también es en una gramática independiente del contexto.

c. Toda gramática de tipo 0 puede transformarse en una gramática sensible al contexto equivalente.

d. Toda gramática de tipo 0 sin estructura de frase puede transformarse en una gramática equivalente de tipo 0 con estructura de frase.

a, b, d

Marque las afirmaciones verdaderas(mas de una):

a. Si la cardinalidad del conjunto cociente Q/E0 es 3, es imposible que la cardinalidad de Q/E1 sea 2.

b. Si Q/E0 = Q/E1 entonces el autómata finito es mínimo.

c. En un autómata de 6 estados, Q/E3 siempre es Q/E.

d. Para determinar si dos autómatas finitos son equivalentes bastará saber si sus autómatas mínimos son isomorfos.

c, d

Marque las afirmaciones verdaderas(mas de una):

a. Podemos utilizar expresiones regulares para describir cualquier lenguaje independiente del contexto.

b. Para que dos AFD sean equivalentes, su número de estados debe ser el mismo.

c. Todo AFND puede transformarse en un AFD equivalente.

d. Dado un AFD siempre es posible encontrar la expresión regular

correspondiente al lenguaje que acepta.

b, c

Marque las afirmaciones verdaderas(mas de una):

a. Si α es una expresión regular, entonces αα∗=α∗

b. Si α es una expresión regular, entonces αα∗=α∗α

c. Db(a\*(a+b)\*) = (a+b)\*

d. δ(a\*bb ) = λ

b, c, d

Marque las afirmaciones verdaderas(mas de una):

a. Existe algún Autómata a Pila (AP) capaz de reconocer el lenguaje vacío

(L= Ø).

b. Un AP puede carecer de estados finales.

c. A partir de un AP que reconoce un lenguaje por estados finales puede construirse otro AP que reconoce un lenguaje por vaciado de pila.

d. Un AP puede tener un solo estado.

a, b, c, d

Marque las afirmaciones verdaderas (mas de una):

a. El lenguaje L={an+2bn} puede ser reconocido por un AP.

b. Un lenguaje que tiene λ como una de sus palabras puede ser aceptado por algún AP.

c. Si en un AP Γ={Α}, Q={p,q}, siendo p estado inicial, entonces la correspondiente gramática tendrá entre sus reglas S::=(p, A, p) | (p, A, q)

d. f(p, x, R) = (p, R) corresponde al movimiento (p, xB, RP) |- (p, B, RP).

a, b, c

Marque las afirmaciones verdaderas( mas de una):

a. L((0+1)\*)=(L(0) ∪ L(1))\*.

b. Si la ecuación característica correspondiente a un AF es

X1=1 X1+0 X2+0+1 X0, entonces el autómata es no determinista.

c. Un autómata que acepta el lenguaje expresado por λ puede tener dos

estados p (inicial) y q (final) con f(p, λ)=q.

d. Siendo α y β expresiones regulares: (α∗β)∗=λ+(αβ)∗β.

a

Marque las afirmaciones verdaderas:

a. En una máquina de Turing transductora, si la entrada no está bien formada, debe acabar en estado no-final.

b. Toda Máquina de Turing tiene un AFD equivalente.

c. Una máquina de Turing no puede modificar el contenido de la cinta.

d. Una máquina de Turing puede desplazarse varias celdas a la vez después de leer un símbolo.

a, d

Marque las afirmaciones verdaderas ( as de una:

a. En una máquina de Turing: f(p,a)→ (p,a,i) indica que mientras lea “a”, se sigue en el estado p, se re-escribe “a”, y se mueve la cabeza de lectura a la izquierda.

b.En una máquina de Turing: f(p,a)→(p,a,i) indica que cuando se encuentra “a”, se sigue en el estado p, se re-escribe “i”, y se mueve la cabeza de lectura a la izquierda.

c. En una máquina de Turing f(r,a)→(r,c,d) indica que se cambian las “*aes”* encontradas por “*ces*” y se cambia de estado.

d. En una máquina de Turing f(q,1) →(q,1,d) indica que siempre que se encuentra el símbolo “1” se re-escribe.

c

Indique, conforme a la jerarquía de Chomsky, cuál de las siguientes gramáticas es de tipo1:

a. G=({a,b, c}, {S, A, B, C}, S, P={S ::= aAb; S::=Ba; S::=λ; aAbC::=aAbB; aBc ::=b })

b. G=({a,b, c}, {S, B}, S, P={S ::= abc; S::=aBSc; Ba::=aB; Bb::=bb })

c. G=({a,b, c}, {S, A, B, C}, S, P={S ::= aAb; S::=Ba; aAbC::=aAbB; aAbC::=aabC; BCc::=BaAbc})

d. G=({a,b}, {S, A, B}, S, P={S ::= aA; S::=bS; A::= λ; A::=bB; A::=aS; A::=b; B::=bB })

b

Indique cuál de las siguientes afirmaciones relacionadas con la Formal Normal del Chomsky es cierta:

a. Una gramática está en FNC si todas las reglas tienen la parte derecha comenzando con un terminal seguido opcionalmente de uno o varios No Terminales.

b. Una gramática bien formada está en FNC si las partes derechas de todas sus reglas de producción tienen como máximo dos símbolos y en tal caso, éstos son No Terminales.

c. Dada una Gramática siempre es posible encontrar otra Gramática en FNC equivalente.

d. Para obtener la FNC equivalente a una gramática dada es necesario que ésta no tenga recursividad a izquierdas.

c

Dado un AF de dos estados en el que X0 = 1X0 + 0X1 + 0 es la ecuación característica del estado inicial y X1 = 1X1+1+0X1+0+λ es la ecuación característica del estado final, indique cuál de las siguientes afirmaciones es cierta:

a. El lenguaje aceptado por el AF es (1+0) (1+0+ λ )\*.

b. λ pertenece al lenguaje aceptado por el AF.

c. El lenguaje aceptado por el AF es 1\*0(1+0)\*

d. El lenguaje aceptado por el AF es (1+0)\*+(1+0+ λ ).

b

Dado el siguiente Autómata Finito, indique la opción **correcta**:

a. L(AF)=ab\*

**b. L(AF)=a+**λ**+(a+**λ**)bb***

c. L(AF)=(a+λ)bb\*

d. L(AF)=a+abb\*+bb\*

d

4. Dada la expresión regular R = (a+b)a\* + b\*(a+b), indique cuál de las siguientes afirmaciones es cierta:


1. δ(R)=λ
2. Dab(R)=(a+b)\*a
3. δ (Dab (R))= δ (Da(R))
4. Da(R)=a\*+λ

c

Indique cuál de las siguientes afirmaciones relacionadas con la Formal Normal del Greibach es cierta:

a- La gramática con axioma C y reglas de producción P={ C::=a; C::=b|Ab; A::=Ba; B::=b} es una gramática en FNG.

b. Para transformar una Gramática en su equivalente en FNG es necesario partir de una gramática limpia y bien formada sin axioma inducido.

c. La gramática con axioma S y reglas de producción P={ S::=a; S::=bAB; A::=a; B::=b} es una gramática en FNG.

d. La gramática con axioma S y reglas de producción P={ S::=a; S::=Ab; A::=Ba; B::=b} es una gramática en FNG.

b

Dada la siguiente Máquina de Turing y admitiendo que el contenido de la cinta es D y que la cabecera de L/E está situada sobre este símbolo, indique cuál será la situación final de dicha máquina:

a. La cinta contiene la letra C y la máquina se para en un estado no final.

b. La cinta contiene 1111 y la máquina se para en un estado final.

c. La cinta contiene DCBA y la máquina se para en un estado final.

d. La cinta contiene 11111 y la máquina se para en un estado final.

a

Si a y B son EERR y L(a) y L(B) los lenguajes que representan, indique cuál de las siguientes relaciones es falsa: \n a. L( λ )=Ø \n b. L(a+B)=L(a)UL(B)

c. L(a•B)=L(a)•L(B)

d. L(a \*) = L(a)\*

d

Admitiendo que R0 es una expresión regular sobre Σ={a, b} y que:

indique cuál de las siguientes gramáticas genera el lenguaje representado por R0:

a. G=({a, b}, {R0, R1, R2}, R0, P = {R0 ::=aR1 | a | bR2 | b; R1 ::= aR1 | a | bR2 | b; R2 ::= aR0 | a | bR2 | b })

b. G=({a, b}, {R0, R1, R2}, R0, P = {R0 ::= aR1 | bR2 | b; R1 ::= aR1 | bR0 | b; R2 ::= aR0 | a | bR2 | b })

c. G=({a, b}, {R0, R1, R2}, R0, P = {R0 ::= λ | aR1 | a | bR2 | b; R1 ::= aR1 | a | bR2 | b; R2 ::=λ | aR0 | a | bR2 | b })

d. G=({a,b},{R0,R1,R2},R0,P={R0 ::=λ|aR1 |bR2 |b;R1::=aR1 |bR2|b; R2 ::= aR0 | a | bR2 | b })

c

Dado el siguiente Autómata Finito indique la opción correcta:

a. Se trata de un AFD mínimo.

b. Se trata de un AFD sin sumidero.

c. Los estados q1 y q2 son equivalentes.

d. Los estados q0, q1 y q2 son E1 equivalentes.

b

Dado un AFD=(Σ, Q, F, q0, F), indique cuál de las siguientes afirmaciones es falsa:

a. El estado p en Q es accesible desde q en Q si existe x en Σ\* tal que f'(q, x)=p.

b. Si AFD es conexo, podemos obtener a partir de él otro autómata equivalente no

conexo eliminando los estados inaccesibles desde el estado inicial.

c. AFD es conexo si todos los estados de Q son accesibles desde q0.

d. Si f'(q0, x)=p con p en F entonces L(AFD) != Ø.

a

Dado el AP definido por (Σ, T, Q, A, q0, f, F) en el que Σ={a, b}; T={A, Z0, Z1}; \n Q={q0, q1, q2, F} indique cuál de las siguientes transiciones identifica al autómata como no determinista:

a. f(q0, a, A )=(q1, Z1). f(q0, λ, A )=(q2, Z0)

b. f(q0, a, A )=(q1, Z1). f(q0, b, A )=(q2, Z0)

c. f(q0, a, A )=(q1, Z1). f(q0, a, Z1 )=(q2, Z0)

d. f(q0, a, A )=(q1, Z1). f(q0, a, Z1 )=(q1, Z1)

d

Indique cuál de las siguientes afirmaciones relacionadas con los Lenguajes Formales es falsa:

a. El Universo del discurso se define como el conjunto de todas las palabras que se pueden formar con los símbolos de un alfabeto.

b. El Universo del discurso contiene un número infinito de palabras.

c. El alfabeto es uno de los lenguajes generados por el mismo.

d. La potencia i-ésima de un lenguaje se corresponde con la potencia i-ésima de todas

sus palabras.

c

Dado el APv = ({0,1}, { Z, A,B}, {p}, Z, p, f, ɸ) con función de transición:

\
Indique cuál de las siguientes expresiones no se corresponde con una regla de producción de la Gramática tipo 2 equivalente:

a. (pAp) ::= 1

b. (pZp) ::= λ

c. S ::= (pZp)|(pAp)|(pBp)

d. (pZp) ::= 0 (pBp)(pAp)(pZp) \n

c

Dado el siguiente Autómata Finito indique la opción falsa:

a. f''(q0, 01)={q1, q2}

b. f''(q0, 111)= {q1, q2}

c. f''(q0, 011)={q2}

d. f''(q0, 01)= f''(q0, 1)

b

Indique cuál de las siguientes afirmaciones relacionadas con la Máquina de Turing Universal, es verdadera:

a. Toda MT Universal permite determinar si otra MT parará o no para una palabra dada.

b. Toda MT universal contiene en su cinta la descripción de otra MT y el contenido de la

cinta de dicha MT.

c. Toda MT Universal utiliza el lenguaje binario para las entradas.

d. Toda MT Universal actúa como Transductora.

a

Dada G=({a,b}, {S, A, B, C}, S, P={S ::= aA | b | bC; C ::= aA | b | bC; A ::= bA}), indique cuál de las siguientes afirmaciones es cierta:

a. Posee reglas superfluas.

b. Según la jerarquía de Chomsky es una gramática de Contexto Libre.

c. Es una gramática limpia y bien formada.

d. Posee símbolos inaccesibles.

d

Dada G=({a,b}, {S, A}, S, P={S ::= aA | b | bS; A ::= bA}) indique cuál de las siguientes gramáticas se corresponde con una G3LI equivalente limpia y bien formada.:

a. G=({a,b}, {S, A, C}, S, P={S ::= b | Cb; C ::= b|Cb|aA; A::=a|Ab})

b. G=({a,b}, {S, A}, S, P={S ::= b | λ ; A::= b|Ab})

c. G=({a,b}, {S, A, C}, S, P={S ::= b | Cb; C ::= b|Cb; A::=Ca|Ab|a})

d. G=({a,b}, {S, C}, S, P={S ::= b | Cb; C ::=b|Cb})

c

Dado el APV = ({0, 1}, { A, U, Z}, {q0, q1}, A, q0, f, Ø), con función de transición :

Indique cuál de las siguientes palabras no pertenece al lenguaje reconocido por el APV: a. 010 \n b. 0110 \n c. 101

d. 00

b

Indique cuál de las siguientes afirmaciones relacionadas con el algoritmo de paso de Gramática Tipo 2 a APv es falsa:

a. La gramática de partida debe estar en FNG.

b. Si A::=aZ es una producción de la G2, entonces f(q,a,A)={(q, λ)} es una transición del autómata.

c. El APv resultante es de un solo estado.

d. Si S::= λ es una producción de la G2, entonces f(q, λ, S)={(q, λ)} es una transición del autómata.

a

Indique, conforme a la jerarquía de Chomsky, cuál de las siguientes gramáticas es de Tipo1:

a. G=({a,b, c}, {S, A, B, C}, S, P={S ::= Ab; Ab ::= BCb; B ::= b | bB; C ::=c})

b. G=({a,b, c}, {S, A, B}, S, P={S ::= abc; S::=aBc; aB::=AB; AB::=abc })

c. G=({a,b, c}, {S, A, B, C}, S, P={S ::= ab; Ab ::= acb |Bb; B ::= BC; BC ::= BaC | Ab})

d. G=({a,b, c}, {S, A, B}, S, P={S ::= ab|ABC; A::= aa |B | BC; B ::= bb|bbB; C ::= c})

c

Indique cuál de las siguientes afirmaciones relacionadas con los Autómatas Finitos Deterministas es **falsa**:

a. Se denomina lenguaje asociado a un AFD al conjunto de todas las palabras aceptadas

por dicho autómata.

b. Si un AFD carece de estados finales, el lenguaje que reconoce es el lenguaje vacío.

c. Un AFD nunca puede reconocer la palabra vacía.

d. Si todos los estados de un AFD son estados finales el lenguaje que reconoce dicho AFD

es el lenguaje universal.

c

Indique cuál de las siguientes afirmaciones relacionadas con el algoritmo de transformación de gramática en FNG a APv es falsa:

a. El APv resultante tiene un único estado.

b. El símbolo inicial de pila se corresponde con el axioma de la gramática.

c. En cada transición sólo está permitido escribir un símbolo en la pila.

d. El alfabeto de entrada se corresponde con el conjunto de símbolos terminales de la gramática.

b

Dado el siguiente AFND indique cuál de las siguientes afirmaciones es **verdadera**:

a. Todas las palabras que terminan en 1 son rechazadas por el AFND.

b. f’’(q1, 00)={q1,q2}

c. Todas las palabras aceptadas por el

AFND terminan en 0.

d. f’’(q0,0)=q3

c

Indique cuál de las siguientes afirmaciones relacionadas con los Autómatas a Pila es verdadera:

a. Todo lenguaje independiente del contexto es aceptado por un autómata de pila determinista.

b. Una palabra es aceptada por un autómata a pila por vaciado si, tras leer la palabra, la pila está vacía y se ha alcanzado un estado final.

c. En un autómata a pila determinista, ciertas transiciones pueden no estar definidas.

d. Todo autómata a pila con transiciones independientes de la entrada es no determinista.

a

Indique cuál de los siguientes tipos de autómatas tiene mayor capacidad computacional:

a. Máquinas de Turing.

b. Autómatas Finitos.

c. Autómatas a Pila.

d. Autómatas Probabilísticos.

d

Indique cuál de las siguientes afirmaciones relacionadas con la palabra vacía (λ) es falsa:

a. La palabra vacía es aquella cuya longitud es cero.

b. La palabra vacía se puede construir sobre cualquier alfabeto.

c. La palabra vacía es el elemento neutro de la concatenación (de palabras).

d. La palabra vacía es el elemento neutro de la unión (de palabras).

c

Dado el siguiente AFD indique cuál de las siguientes afirmaciones es **falsa**:

a. f’(p,10)=s.

b. f’(r, 011)=f’(s,11).

c. El lenguaje reconocido es L={λ, 0\*1}.

d. Se trata de un AFD mínimo.

b

Indique cuál de las siguientes afirmaciones relacionadas con las clases de equivalencia de un AFD es falsa:

a. Si Q/En=Q/En+1 entonces Q/En=Q/En+i ∀ i=2,3,...

b. Si |Q|=n y n>1, siempre se verifica que Q/E1=Q/E2.

c. Si |Q/E0|=1 entonces Q/E0 = Q/E.

d. Si p En q y f(p,a) En f(q,a) ∀ a en Σ, entonces se verifica que p En+1 q.

c

Dados Σ={a, b, c}, y x=abbbc indique cuál de las siguientes afirmaciones es **cierta**:

a. |x|=3.

b. x^2=aabbbcc.

c. La palabra refleja de x es cbbba.

d. (x^-1)(x^1)=x.

c

Dado el APV = ({a, b}, { Z, A, B}, {q0, q1}, Z, q0, f, Ø), con función de transición

Indique cuál de las siguientes expresiones no se corresponde con una regla de producción de la Gramática tipo 2 equivalente:


1. (q0Zq0) ::= a(q0A q0)( q0Zq0) | a(q0A q1)(q1Z q0)
2. S::= q0Zq0| q0Zq1
3. (q0Aq1) ::= a(q1A q0)( q0Zq0) | a(q1A q1)( q1Zq0)
4. (q1Zq1) ::= λ

a

Indique cuál de las siguientes afirmaciones relacionadas con lenguajes es **falsa**:

a. El lenguaje vacío es aquel que contiene la palabra vacía.

b. Un alfabeto es uno de los lenguajes generados por el mismo.

c. La concatenación de lenguajes y la unión de lenguajes constituyen, junto con el

alfabeto, un binoide libre.

d. La clausura positiva de un lenguaje L es el lenguaje obtenido uniendo el lenguaje L con

todas sus potencias posibles excepto L^0.

d

Dado el APV = ({a, b}, { Z, A, B}, {q0, q1}, Z, q0, f, Ø), con función de transición :

Indique cuál de las siguientes afirmaciones es cierta:

a. Se trata de un APv no determinista.

b. El lenguaje reconocido por el APv es el lenguaje vacío.

c. No es posible encontrar una Gramática en Forma Normal de Chomsky que genere el

lenguaje aceptado por el APv.

d. La palabra más corta reconocida por el APv es abaa

d

Indique cuál de las siguientes palabras no es reconocida por la siguiente Máquina de Turing:

a. aac \n b. acab

c. caab

d. cabca

d

Indique cuál de las siguientes afirmaciones es falsa:

a. El Teorema de análisis de Kleene dice que “Todo lenguaje aceptado por un AF es un

lenguaje regular”.

b. La solución formal al problema de síntesis consiste en derivar la ER de partida, obtener

una G3LD y finalmente un AF.

c. Existe un algoritmo recursivo que permite construir el AF que acepta el lenguaje

representado por una expresión regular.

d. La Solución de Arden resuelve cualquier ecuación.

b

Dado el siguiente AF y admitiendo que X0, X1 y X2 representan a las ecuaciones características asociadas a los estados q0, q1 y q2 respectivamente, indique cuál de las siguientes afirmaciones es falsa:

a. X0 tiene 4 términos.

b. X2=Ø \n c. X1=b\*a \n d. X0=ab\*a+b+λ

c

Dada G3LD=({0,1,2}, {S, A, B}, S, P={S ::= 0B | 1; B ::= 1S | 0 |2A; A ::= 0 | 2A}), indique cuál de las siguientes gramáticas se corresponde con la G3LI equivalente:

a. G=({0,1,2}, {S, A, B}, S, P={S ::= B0 | 1; B ::= S1 | 0 |A2; A ::= 0 | A2})

b. G=({0,1,2}, {S, A, B, F}, F, P={F ::= A0 | S1 | B0; S ::= B1; B ::= S0;A ::= A2 | B2})

c. G=({0,1,2},{S,A,B,C},S,P={S::=C1|1|A0|B0;C::=B1;B::=C0|0;A::=B2| A2})

d. G=({0,1,2}, {S, A, B}, S, P={S ::= B0 | 1; B ::= S1 | A; A ::= 0 | A2})

b

Dado el siguiente Autómata Finito, indique cuál de las siguientes gramáticas se corresponde con la G3LD limpia y bien formada equivalente:

a. G=({a,b}, {S, A, B}, S, {S ::= aS | bA; A ::= aB; B ::= bA})

b. G=({a,b}, {S, A, B}, S, {S ::= aS | bA | b | aB | λ; A ::= aB; B ::= bA | b})

c. G=({a,b}, {S, A, B}, S, {S ::= aS | bA | b | λ; A ::= aB; B ::= bA | b})

d. G=({a,b}, {S, A, B}, S, {S ::= aS | bA | b | aB; A ::= aB; B ::= bA | b})

a

Indique cuál de las siguientes afirmaciones relacionadas con las Máquinas de Turing es falsa:

a. El espacio en blanco siempre forma parte del alfabeto de entrada de la máquina. \n b. Una Máquina de Turing puede simular la lógica de cualquier algoritmo de un computador. \n c. El cabezal de un Máquina de Turing admite tres tipos de movimientos. \n d. Si en una máquina de Turing una transición no es posible, la máquina se detiene.

b

Si a y B son dos expresiones regulares, indique cuál de las siguientes relaciones es falsa:

a. (a\*)\*=a\*

b. (a•B)=(B•a) \n c. λ+aa\*=a\* \n d. (a\*+B\*)\*=(a+B)\*

c

Indique cuál de las siguientes afirmaciones relacionadas con lenguajes es falsa:

a. La concatenación de lenguajes y la unión de lenguajes constituyen, junto con el

alfabeto, un binoide libre.

b. La clausura positiva de un lenguaje L es el lenguaje obtenido uniendo el lenguaje L con

todas sus potencias posibles excepto L^0.

c. El lenguaje vacío es aquel que contiene la palabra vacía.

d. Un alfabeto es uno de los lenguajes generados por el mismo.

b

Indique cuál de las siguientes afirmaciones relacionadas con las clases de equivalencia de un AFD es falsa:

a. Si Q/En=Q/En+1 entonces Q/En=Q/En+i ∀ i=2,3,...

b. Si |Q|=n y n>1, siempre se verifica que Q/E1=Q/E2.

c. Si |Q/E0|=1 entonces Q/E0 = Q/E.

d. Si p En q y f(p,a) En f(q,a) ∀ a en Σ, entonces se verifica que p En+1 q.

a

Dado el siguiente Autómata Finito, indique cuál de las siguientes gramáticas se corresponde con la G3LD limpia y bien formada equivalente:

a. G=({a,b}, {S, A, B}, S, {S ::= aS | bA | b | aB | λ;; A ::= aB; B ::= bA | b})

b. G=({a,b}, {S, A, B}, S, {S ::= aS | bA; A ::= aB; B ::= bA})

c. G=({a,b}, {S, A, B}, S, {S ::= aS | bA | b | λ;; A ::= aB; B ::= bA | b})

d. G=({a,b}, {S, A, B}, S, {S ::= aS | bA | b | aB; A ::= aB; B ::= bA | b})

d

Dada G3LD=({0,1,2}, {S, A, B}, S, P={S ::= 0B | 1; B ::= 1S | 0 |2A; A ::= 0 | 2A}), indique cuál de las siguientes gramáticas se corresponde con la G3LI equivalente:

a. G=({0,1,2}, {S, A, B}, S, P={S ::= B0 | 1; B ::= S1 | 0 |A2; A ::= 0 | A2})

b. G=({0,1,2}, {S, A, B, F}, F, P={F ::= A0 | S1 | B0; S ::= B1; B ::= S0;A ::= A2 | B2})

c. G=({0,1,2}, {S, A, B}, S, P={S ::= B0 | 1; B ::= S1 | A; A ::= 0 | A2})

d. G=({0,1,2},{S,A,B,C},S,P {S::=C1|1|A0|B0;C::=B1;B::=C0|0;A::=B2| A2})

a

Indique cuál de los siguientes tipos de autómatas tiene mayor capacidad computacional:

a. Máquinas de Turing.

b. Autómatas Finitos.

c. Autómatas Probabilísticos.

d. Autómatas a Pila.

c

Dado el siguiente AF y admitiendo que X0, X1 y X2 representan a las ecuaciones características asociadas a los estados q0, q1 y q2 respectivamente, indique cuál de las siguientes afirmaciones es falsa:

a. X0 tiene 4 términos.

b. X1=b\*a \n c. X2=Ø \n d. X0=ab\*a+b+λ

c

Indique cuál de las siguientes afirmaciones relacionadas con la palabra vacía (λ) es falsa:

a. La palabra vacía es aquella cuya longitud es cero.

b. La palabra vacía se puede construir sobre cualquier alfabeto.

c. La palabra vacía es el elemento neutro de la unión (de palabras).

d. La palabra vacía es el elemento neutro de la concatenación (de palabras).

b

Indique cuál de las siguientes palabras no es reconocida por la siguiente Máquina de Turing:

a. aac

b. cabca

c. acab

d. caab

a

Indique cuál de las siguientes afirmaciones relacionadas con los Autómatas Finitos Deterministas es falsa:

a. Un AFD nunca puede reconocer la palabra vacía.

b. Se denomina lenguaje asociado a un AFD al conjunto de todas las palabras aceptadas

por dicho autómata.

c. Si un AFD carece de estados finales, el lenguaje que reconoce es el lenguaje vacío.

d. Si todos los estados de un AFD son estados finales el lenguaje que reconoce dicho AFD

es el lenguaje universal.

d

Dado el siguiente AFND indique cuál de las siguientes afirmaciones es verdadera:

a. Todas las palabras que terminan en 1 son rechazadas por el AFND.

b. Todas las palabras aceptadas por el AFND terminan en 0.

c. f’’(q0,0)=q3

d. f’’(q1, 00)={q1,q2}

b

Dados Σ={a, b, c}, y x=abbbc indique cuál de las siguientes afirmaciones es cierta:


1. |x|=3.
2. La palabra refleja de x es cbbba.
3. x2=aabbbcc.
4. (x^-1)(x^1)=x.

b

Dado el siguiente AFD indique cuál de las siguientes afirmaciones es **falsa**:

a. Se trata de un AFD mínimo.

b. El lenguaje reconocido es L={λ, 0\*1}.

c. f’(p,10)=s. \n d. f’(r, 011)=f’(s,11).

a

Indique, conforme a la jerarquía de Chomsky, cuál de las siguientes gramáticas es de Tipo1:

a. G=({a,b, c}, {S, A, B, C}, S, P={S ::= Ab; Ab ::= BCb; B ::= b | bB; C ::=c})

b. G=({a,b, c}, {S, A, B}, S, P={S ::= abc; S::=aBc; aB::=AB; AB::=abc })

c. G=({a,b, c}, {S, A, B, C}, S, P={S ::= ab; Ab ::= acb |Bb; B ::= BC; BC ::= BaC | Ab})

d. G=({a,b, c}, {S, A, B}, S, P={S ::= ab|ABC; A::= aa |B | BC; B ::= bb|bbB; C ::= c})a

b

Indique cuál de las siguientes afirmaciones relacionadas con las Máquinas de Turing es falsa:

a. Una Máquina de Turing puede simular la lógica de cualquier algoritmo de un computador.

b. El espacio en blanco siempre forma parte del alfabeto de entrada de la máquina.

c. El cabezal de una Máquina de Turing admite tres tipos de movimientos.

d. Si en una máquina de Turing una transición no es posible, la máquina se detiene

d

Dado el APV = ({a, b}, { Z, A, B}, {q0, q1}, Z, q0, f, Ø), con función de transición :

Indique cuál de las siguientes afirmaciones es cierta:

a.Se trata de un APv no determinista.

b. El lenguaje reconocido por el APv es el lenguaje vacío.

c. No es posible encontrar una Gramática en Forma Normal de Chomsky que genere el lenguaje aceptado por el APv.

d. La palabra más corta reconocida por el APv es abaa

a

Indique cuál de las siguientes afirmaciones relacionadas con el algoritmo de transformación de gramática en FNG a APv es falsa:

a. En cada transición sólo está permitido escribir un símbolo en la pila.

b. El APv resultante tiene un único estado.

c. El símbolo inicial de pila se corresponde con el axioma de la gramática.

d. El alfabeto de entrada se corresponde con el conjunto de símbolos terminales de la gramática.

c

Si a y B son dos expresiones regulares, indique cuál de las siguientes relaciones es falsa:

a. (a\*)\*=a\*

b. λ+aa\*=a\* \n c. a•B)=(B•a) \n d. (a\*+B\*)\*=(a+B)\*

c

Indique cuál de las siguientes afirmaciones es falsa:

a. El Teorema de análisis de Kleene dice que “Todo lenguaje aceptado por un AF es un lenguaje regular”.

b. La solución formal al problema de síntesis consiste en derivar la ER de partida, obtener una G3LD y finalmente un AF.

c. La Solución de Arden resuelve cualquier ecuación.

d. Existe un algoritmo recursivo que permite construir el AF que acepta el lenguaje representado por una expresión regular.

d

Indique cuál de las siguientes afirmaciones relacionadas con los Autómatas a Pila es verdadera:

a. Todo lenguaje independiente del contexto es aceptado por un autómata de pila determinista.

b. Una palabra es aceptada por un autómata a pila por vaciado si, tras leer la palabra, la pila está vacía y se ha alcanzado un estado final.

c. Todo autómata a pila con transiciones independientes de la entrada es no determinista.

d. En un autómata a pila determinista, ciertas transiciones pueden no estar definidas.

a

Dado el APV = ({a, b}, { Z, A, B}, {q0, q1}, Z, q0, f, Ø), con función de transición :

Indique cuál de las siguientes expresiones **no se corresponde** con una regla de producción de la Gramática tipo 2 equivalente:

a. (q0Aq1) ::= a(q1A q0)( q0Zq0) | a(q1A q1)( q1Zq0)

b. S::= q0Zq0| q0Zq1

c. (q0Zq0) ::= a(q0A q0)( q0Zq0) | a(q0A q1)(q1Z q0)

d. (q1Zq1) ::= λ

d

Indique cuál de las siguientes afirmaciones relacionadas con los distintos tipos de Autómatas es **falsa**:

a. Los Autómatas a Pila tienen mayor capacidad de cómputo que los Autómatas Finitos.

b. Las Máquinas de Turing tienen mayor capacidad de cómputo que los Autómatas a Pila.

c. Los Autómatas Celulares tienen mayor capacidad de cómputo que los Autómatas Finitos.

d. Los Autómatas Finitos Deterministas tienen mayor capacidad de cómputo que los Autómatas Finitos No Deterministas.

b

Indique cuál de las siguientes afirmaciones relacionadas con los Autómatas Finitos Deterministas es cierta:

a. Todo AFD=(∑, Q, f, q0, F) cuyo estado inicial es también final reconoce el Lenguaje Universal.

b. Todo AFD=(∑, Q, f, q0, F) en el que el F=Q reconoce el Lenguaje Universal.

c. Todo AFD=(∑, Q, f, q0, F) en el que no existe estado sumidero reconoce el Lenguaje Universal.

d. No es posible construir un AFD que reconozca el Lenguaje Universal.

d

Dado el alfabeto ∑={a, b}, indique cuál de las siguientes afirmaciones es **falsa**:

a. Si L={a, b, ab, ba} entonces L^1=L

b. Si L={λ,a, b} entonces L+=L\*

c. Si L={ab, a, ba} entonces L=L^-1

d. Si L={a, b} entonces L• Ø=Ø• L={λ }

c

Dada una MT= (∑,Γ, b, {Q}, q0, f, F) indique, cuál de las siguientes afirmaciones es cierta:

a. Una máquina de Turing que actúa como reconocedora se caracteriza porque F=φ

b. En una máquina de Turing que actúa como transductor ∑=Γ

c. En toda máquina de Turing se debe satisfacer que ∑ ⊂ Γ

d. Una máquina de Turing que actúa como transductora es aquella en la que alguna de las transiciones no está definida

a

Indique, cuál de las siguientes afirmaciones referidas a los Autómatas a Pila es cierta:

a. Existen Autómatas a Pila Deterministas para los que el conjunto de estados finales es el conjunto vacío.

b. Todo lenguaje independiente del contexto puede ser reconocido por un Autómata a Pila determinista.

c. Un Autómata a Pila determinista no puede contener transiciones independientes de la entrada.

d. Para cada gramática G dependiente del contexto, existe un Autómata a Pila M tal que L(G)=L(M)

b

Dado el siguiente Autómata Finito, indique cuál de las siguientes afirmaciones es falsa:

a. La expresión regular a\*b(ab)\* representa a todas las palabras reconocidas por el autómata.

b. La ecuación característica asociada al estado final es X1=λ.

c. La ecuación característica asociada al estado inicial tiene tres términos.

d. La solución a la ecuación característica asociada a q2 es X2=(ba)\*b

b

Indique cuál de las siguientes afirmaciones es falsa:

a. Dado un alfabeto, el Lenguaje Universal contiene un número infinito de palabras.

b. Para asegurar que la palabra vacía pertenece al Lenguaje Universal de un alfabeto es necesario conocer los símbolos que componen dicho alfabeto.

c. Los símbolos que componen un alfabeto pueden estar formados por varios caracteres.

d. La longitud de palabra es una magnitud dependiente del alfabeto sobre el que está definida la palabra.

c

Dado el siguiente AFD, indique cuál de las siguientes afirmaciones es correcta:

a. Q/E0={{Q0}, {Q1, Q2, Q3}}

b. Q0 E1 Q1

c. Q2 E1 Q3

d. Q/E0= Q/E

b

Indique cuál de las siguientes afirmaciones relacionadas con el concepto de Ambigüedad es falsa:

a. La propiedad de ambigüedad es indecible.

b. Si una gramática es ambigua, entonces el lenguaje que describe es ambiguo.

c. Una sentencia es ambigua si puede obtenerse por medio de dos o más árboles de derivación diferentes.

d. Una gramática es ambigua si genera al menos una sentencia ambigua.

d

Dada la expresión regular R = (a+b)(ba)\*, indique cuál de las siguientes afirmaciones es falsa:

a. Da(R) = Db(R)

b. δ(R)=φ

c. δ (Da (R))= λ

d. Db(R) = b(ba)\*

d

Dado un alfabeto ∑ y admitiendo que L1 y L2 son dos lenguajes definidos sobre ∑, indique cuál de las siguientes afirmaciones es cierta:

a. Si x∈ L1•L2 entonces x∈L1 ó x∈L2

b. Si x∈ L1•L2 entonces x∈ L2•L1

c. Si x∈L1 entonces x∈L1•L2

d. Si x∈L1 entonces x∈L1∪L2

b

Dada la Máquina de Turing MT = ({1, 0}, {1, 0, b}, b, {p,q,r}, p, f, {r}), con función de transición:

Indique la afirmación verdadera:

a. Acepta la palabra 00

b. Acepta la palabra 101

c. Reconoce el lenguaje definido por L=(0+1)\*1

d. Es una máquina de Turing que actúa como transductor.

a

Dada G={∑T, ∑N, S, P}, indique cuál de las siguientes afirmaciones es cierta:

a. Si G es una gramática sin restricciones, L(G) puede ser descrito por otra G' con

estructura de frases.

b. Si G posee reglas compresoras, entonces se puede asegurar que se trata de una gramática Sensible al Contexto.

c. Si ∀ r∈P se satisface que la parte izquierda está formada por un único símbolo NT, entonces se puede asegurar que G es una Gramática de Contexto Libre.

d. Si ∀ r∈P se satisface que la parte izquierda está formada por un único símbolo NT, entonces se puede asegurar que G es una Gramática Regular.

a

Dado AP=({0, 1, A}, {0, 1, A}, {q0, q1}, A, q0, f, Ø) y admitiendo que (q0, 00, 11A) ⊢ (q1, 0, 1A) es un movimiento del autómata, indique cuál de las siguientes afirmaciones es cierta:

a. La transición que describe el movimiento es f(q0, 0, 1) = ( q1, λ).

b. La transición que describe el movimiento es una transición independiente de la entrada.

c. Tras realizar el movimiento, en la entrada, quedan dos símbolos por leer.

d. La transición que describe el movimiento indica que el Autómata es no determinista

b

Dado el siguiente autómata finito no determinista, seleccione la respuesta **correcta**:

a. La palabra vacía, λ, no pertenece al Lenguaje reconocido por el autómata.

b. q0 está en relación T\* con q3.

c. f''(q0,ba) = {q3}

d. f''(q0,ab) = {q0, q2}

b

Dadas las siguientes reglas de A, A ::= Aa | Aba | b, el resultado de aplicar el algoritmo de eliminación de la recursividad a izquierdas es: \n a. A::=a|ba|aX|baX;X::=b|bX \n b. A::=b|bX;X::=a|ba|aX|baX

c. A::=a|ba|aA|baA;X::=b|bA

d. A::=b|bX;X::=a|ba|aA|baA

c

Dados los autómatas AF1 y AF2, marque la afirmación correcta:

a. AF2 reconoce el lenguaje universal.

b. Son isomorfos.

c. Son equivalentes.

d. Todas las palabras reconocidas por AF2 contienen al menos una b.

a

Dada G =( {a,b}, {S,B,C}, S, P ), P={S ::= a | aB | aC | λ ; B ::= b | bB ; C ::= c}), indique la afirmación correcta:

\
a. AF=\[{a,b}, {S,B,C,F}, f, S, {F}\] con f(S,a)={F, B, C}; f(S, λ)= F; f(B,b)={F, B}; f(C,c)={F} es un AFND que acepta el lenguaje generado por G.

b. AF=\[{a,b}, {S,B,C,F}, f, S, {F}\] con f(S,a)={F, B, C}; f(S, λ)= F; f(B,b)={F, B}; f(C,c)={F} es un AFD que acepta el lenguaje generado por G.

c. Dadas las características de la gramática es imposible encontrar un AF que acepte el lenguaje generado por G.

d. Para poder obtener un AF que acepte el lenguaje generado por G es necesario partir de una G3LI equivalente a G.

b

Dada G=({a, b}, {S, A, B, C, D}, S, P) con P={ S::= a|bA; A::= baB|bC; B ::= b|λ; C::= abC; D::= ab}, indique cuál de las siguientes afirmaciones es falsa:

a. G no posee reglas de redenominación.

b. D es un símbolo no generativo.

c. A::=bC es una regla superflua.

d. B::=λ es una regla no generativa.

d

Dado el APV = (Σ={0,1}, Γ={Z,X}, Q={p, q}, Z, p, f, ɸ) y admitiendo que cuando la cadena de entrada es 0011, la sucesión de descripciones instantáneas es: \n (p, 0011, Z) ⊢ (p, 011, XZ) ⊢ (p, 11, XXZ) ⊢ (q, 1, XZ) ⊢ (q ,λ, Z) ⊢ (q, λ, λ)

Indique cuál de las siguientes afirmaciones es correcta:

\
a. f(p, 0, Z) = (p,X) y f(p, 0, X) = (p, X) son transiciones del autómata.

b. f(p, 1, XXZ)=(q, XZ) es una transición del autómata e indica que el autómata es no

determinista.

c. El estado inicial es p y el estado final es q

d. f(p, 0, Z) = (p,XZ) y f(p, 0, X) = (p, XX) son transiciones del autómata.