Foros aprenderaprogramar.com
Didáctica y divulgación de la programación

PREGUNTA: Dado el alfabeto Σ = {0, 1}, se define L como el lenguaje formado por las cadenas que cumplen que N(0) = N(1) + 1 donde N(0) es el número de apariciones del símbolo 0 y N(1) es el número de apariciones del símbolo 1. Indicar cuál de las siguientes gramáticas independientes del contexto genera L.

a)   S -- > CB | BC | 0C1 | 1C0 | 0
       C -- > 0C1 | 1C0 | 0
       B -- > 0B1 | 1B0 | 01 | 10


b)   S -- > 0A1 | 0
       A -- > 0A1 | 0B | 0
       B -- > 0B | 0


c)   S -- > CB | BC | 0C1 | 1C0 | 0 | ε
       C -- > 0C1 | 1C0 | 0
       B -- > 0B1 | 1B0 | 01 | 10










RESPUESTA: la opción correcta es la a).

El lenguaje comprende las cadenas donde el número de ceros es igual al número de unos más uno, por ejemplo: 100 (aparece cero una vez más que el 1), 11000, 1110000.
Como no indica nada relativo al orden se admite también 010, 001, 00011, 01010, etc.
¿Se admite 0? Sí, caso de que el número de unos es cero y el número de ceros es una unidad más que el número de unos. ¿Se admite 1? No, en este caso el número de ceros tiene que ser dos. ¿Se admite 01? No ¿Se admite 10? No ¿Se admite la cadena vacía? No, porque no cumple que el número de ceros sea uno más que el número de unos.

La opción b) no permite derivar cadenas que empiecen por 1, por tanto no representa el lenguaje.

La opción c) se descarta por admitir la cadena vacía.

 La opción a) permite derivar el cero, cadenas que empiecen por 0 o por 1 y que permiten añadir pares de ceros y unos en cualquier orden para cerrarse han de derivar la C a cero, lo cual supondrá que la cadena tenga un número de ceros una unidad superior al número de unos.  Respondemos por tanto la opción a).

PREGUNTA: Las redes de operadores se utilizan en:

a) El modelo abstracto de cómputo funcional

b) El modelo abstracto de cómputo lógico

c) El modelo abstracto de cómputo imperativo

d) El modelo abstracto de cómputo flujo de datos







RESPUESTA: la opción correcta es la d).

Pregunta difícil de responder puesto que para poder responderla hemos hacerlo por pura memorización. Para responderla tenemos que recordar esto: “El modelo de cómputo de flujo de datos hace que los programas se basen en un conjunto de operadores (por ejemplo +, - , *, /, etc.) que forman una red. Cada operador se representa como un cuadrado con entradas numéricas y salidas (el resultado de aplicar el operador a las entradas)."

PREGUNTA: Dado el lenguaje compuesto por las cadenas de longitud finita formadas por todas aquellas combinaciones de símbolos del alfabeto Σ = {a, b, c, d, e}. ¿Se puede construir un autómata a pila que cuente el número de vocales de una cadena de entrada y utilice únicamente la cima de la pila?:

a) Sí, pero se tiene que enseñar al autómata a sumar.

b) Sí, utilizando notación no decimal.

c) Sí, pero sólo teniendo en cuenta que las cadenas de entrada tienen una longitud finita.

d) Sí, si se cumplen todas las condiciones anteriores.







RESPUESTA: la opción correcta es la d), pero ver comentarios.

Esta pregunta es un tanto confusa. El enunciado no es claro, con lo cual no podemos dar un razonamiento lógico como en otras preguntas. Nos limitamos a indicar que la respuesta “oficial” es que “todo lo que hace un autómata a pila es enseñado, por lo que a) es cierta. La notación decimal sólo permitiría contar hasta 9, por lo que hemos de usar notación no decimal y b) es cierta. c) es cierta porque si no no se podrían reconocer cadenas. Y d) es por tanto cierta.

No comments…

PREGUNTA: Dado el alfabeto Σ = {a, e, i, O, u}. Definimos el concepto sílaba como cualquier ordenación de los cinco elementos del alfabeto sin repetición. Si definimos un lenguaje cuyas palabras se forman como la concatenación de un número impar de sílabas, podemos afirmar que:

a) El lenguaje es regular.

b) El lenguaje es independiente del contexto finito no regular.

c) El lenguaje es independiente del contexto infinito no regular.

d) El lenguaje es recursivamente enumerable no independiente del contexto.








RESPUESTA:

Un número impar es infinito, por tanto descartamos la opción b.

Ahora nos preguntamos ¿la máquina más simple que puede reconocer este lenguaje será un autómata finito (en cuyo caso será lenguaje regular), un autómata a pila (en cuyo caso será independiente del contexto infinito no regular) o una máquina de Turing (en cuyo caso será recursivamente enumerable, reconocible por máquinas de Turing).

¿Qué son sílabas? Son sílabas aeiou, aeiuo, aeoiu, aeoui… hasta concluir con un número finito de sílabas (puede ser grande, pero es finito). Si es finito, toda sílaba se puede representar con un autómata finito no determinista que tuviera muchas ramas, cada una de las cuales representa una sílaba (por ejemplo una rama sería a-e-i-o-u, otra rama sería a-e-i-u-o, y así sucesivamente).

El carácter impar de una concatenación de sílabas lo podemos representar con un autómata finito no determinista que reconoce tres sílabas determinadas una después de otra y con un nuevo carácter vuelve a la segunda sílaba (a su primer carácter, de modo que ahí le faltarían dos sílabas para llegar a aceptación).

Posiblemente salga un autómata de cientos o miles de estados, pero se podría representar usando un autómata finito no determinista por lo que respondemos la opción a), el lenguaje es regular.

Esta pregunta no es nada sencilla de responder… así que no te sientas mal si no has sido capaz de responderla 

PREGUNTA: Respecto al número de elementos podemos afirmar que:

a) Las secuencias enlazadas son ilimitadas y las formaciones limitadas

b) Las secuencias enlazadas y las formaciones son limitadas

c) Las secuencias enlazadas y las formaciones son ilimitadas

d) Las secuencias enlazadas son limitadas y las formaciones ilimitadas







RESPUESTA:

Pregunta difícil de entender. ¿Qué están preguntando? Poco claro, y si no sabemos qué se pregunta dar una respuesta es difícil. Voy a dar una respuesta haciendo una suposición.

Si suponemos que con secuencias enlazadas se refieren a una estructura de datos enlazada a través de punteros como una lista enlazada, son ilimitadas ya que podemos añadir o eliminar elementos dinámicamente.

Si suponemos que con formaciones se refieren a arrays (vectores o matrices tradicionales), éstos en C/C++ tienen un tamaño fijo y que no puede cambiar, por tanto diremos que son limitadas.

Respondemos por tanto la opción a).

PREGUNTA: Dado el siguiente autómata


podemos afirmar:
 
a) Reconoce el lenguaje L definido por la expresión regular x*y*

b) Reconoce el lenguaje L = {xⁿyⁿ : n > 0}

c) Reconoce el lenguaje L = {xⁿy²ⁿ : n > 0}

d) Reconoce un lenguaje que se puede expresar como la unión de dos lenguajes independientes del contexto.





RESPUESTA: la opción correcta es la d).

Se trata de un autómata a pila que reconoce la gramática:

S -- > A
S -- > B
A -- > xAy
B -- > xxBy
A -- > xy
B --  > xxy

La gramática forma dos ramas de lenguaje, la que deriva de la A y la que deriva de la B.

A partir de la A tenemos cadenas que empiezan por x y tienen un número de x igual al número de y´s, por tanto admite xy, xxyy, xxxyyy, etc., sublenguaje xⁿyⁿ

A partir de la B tenemos cadenas que empiezan por x y tienen el doble de x que de y´s, por tanto admite xxy, xxxxyy, xxxxxxyyy, sublenguaje x²ⁿyⁿ

El lenguaje admitido por el autómata podríamos definirlo como L = { xⁿyⁿ U x²ⁿyⁿ tal que n >0 } donde U representa unión.

¿Reconoce el lenguaje x*y*? No, porque x*y* admite la cadena vacía y este lenguaje no la admite.

 ¿Reconoce el lenguaje L = {xⁿyⁿ : n > 0} ? Sí, este es un lenguaje independiente del contexto. Pero además reconoce más cadenas que las definidas por este lenguaje.

¿ Reconoce el lenguaje L = {xⁿy²ⁿ : n > 0} ? Sí, este es un lenguaje independiente del contexto. Pero además reconoce más cadenas que las definidas por este lenguaje.

¿Reconoce un lenguaje que se puede expresar como la unión de dos lenguajes independientes del contexto.? Sí, esta es la respuesta más acertada (aunque las respuestas b) y c) también serían verdaderas, pero incompletas o “no del todo exactas”).

Respondemos por tanto la opción d).

Dado el lenguaje L = {xⁿyⁿzⁿ : n > 0} que es reconocible con un autómata a pila con dos pilas. ¿Es posible construir una máquina de Turing que simule el uso de esas dos pilas?

a) Verdadero.

b) Falso.





RESPUESTA: la opción correcta es la a).

La máquina de Turing es la máquina con mayor capacidad de reconocimiento de entre las que se toman en consideración en teoría de autómatas, por tanto todo autómata que reconozca un lenguaje puede ser emulado por una máquina de Turing.

PREGUNTA: Suponga que extendemos los operadores utilizados para expresar las expresiones regulares con el operador " ' ", el cual significa que aquello a lo que eleve se puede repetir una o más veces. Por ejemplo:

• a' = a, aa, aaa, aaaa, ...

• (ab)’ = ab, abab, ababab, abababab, ...

• (a + b)' = a, b, aa, bb, ab, ba, aaa, aab, aba, baa, abb, bab, bba, bbb ...

Con este operador, ¿se amplia la capacidad de expresión de las expresiones regulares?, ¿se puede definir la expresión regular de un lenguaje que no se podía con anterioridad?


a) Si

b) No





RESPUESTA: la opción correcta es la b).

La repetición de un símbolo a una o más veces se puede representar en lenguajes regulares de dos maneras: como a+ o bien como aa*.

Por tanto todo lo que se puede hacer con este operador ya se podía hacer con los operadores existentes para las expresiones regulares. No se amplía la capacidad de expresión de las expresiones regulares. No se puede definir ninguna expresión que no se pudiera definir con anterioridad. Por tanto la respuesta es la b), este operador no aporta nada nuevo.

PREGUNTA: Sea L1 el lenguaje definido por la gramática

S -- > xxxxxAyy, A -- > xxxxxAyy, S -- > xxxxxxxBy, B -- > xxxxxxxBy, A -- > λ, B -- > λ,

con símbolo inicial de la gramática S. Sea L2 el lenguaje formado por las cadenas del lenguaje L1 con una cardinalidad máxima de 35 letras. Podemos afirmar:


a) Que el lenguaje L2 es un lenguaje regular por estar acotada la cardinalidad de las cadenas, y que se puede reconocer con un autómata finito determinista de 7 estados que es mayor que el número máximo de producciones utilizadas en la generación de las palabras.

b) Como la cardinalidad de las palabras del lenguaje L2 está acotada a un valor que asegura que sólo se pueda utilizar o la producción A -- > λ, o la producción B -- > λ y no las dos para la generación de todas las palabras del lenguaje, entonces podemos asegurar que se puede reconocer el lenguaje L2 con un autómata a pila determinista.

c) Como el lenguaje L2 es regular y puede ser reconocido por un autómata finito, el lenguaje L1 tiene que ser regular.

d) Como el lenguaje L1 es reconocido por un autómata a pila no determinista, sólo un autómata a pila no determinista puede reconocer el lenguaje L2







RESPUESTA: La opción correcta es la b).

El lenguaje L2 está formado por un número finito de cadenas, por tanto puede ser representado por un autómata finito y por tanto es un lenguaje regular.

La gramática de L1 podemos verla como formada por dos ramas:

S -- > xxxxxAyy, A -- > xxxxxAyy, S -- > xxxxxxxBy, B -- > xxxxxxxBy, A -- > λ, B -- > λ

La rama A nos lleva a cadenas con un número de x´s múltiplo de 5, y un número de y´s múltiplo de 2 de la forma n*(x⁵y²) donde n>0 . Quedan dentro del lenguaje cinco x´s seguidas de dos y´s, diez x´s seguidas de 4 y´s, quince x´s seguidas de seis y´s, etc.

La rama B nos lleva a cadenas con un número de x´s múltiplo de 7 y un número de y´s la séptima parte del número de x´s, de la forma n*(x⁷y) donde n>0. Quedan dentro del lenguaje siete x´s seguidas de una y, catorce x´s seguidas de dos y´s, veintiuna x´s seguidas de tres y´s, etc.

¿L1 podemos representarlo con una expresión regular? No, podemos apreciar que necesitamos contar: por cada 5 x´s contadas añadir 2 y´s al final por ejemplo requiere que contemos las x´s. Si necesitamos contar no es un lenguaje regular y no es representable con un autómata finito.

¿L1 podemos representarlo con un autómata a pila? Por cada cinco x´s podemos añadir un símbolo a la pila, y luego por cada 2 y´s desapilar el símbolo añadido previamente, por tanto podemos representarlo con un autómata a pila determinista y podemos decir que es un lenguaje independiente del contexto.

Analizamos las opciones:

Opción a) Si tenemos cadenas de hasta 35 letras que tenemos que reconocer una a una vamos a necesitar muchos estados, por lo menos 35 pero como hay muchas variantes podríamos estar hablando de bastantes decenas más de estados necesarios. Tener en cuenta que no podemos crear un bucle en el autómata porque entonces no podríamos verificar que la palabra más grande tenga 35 letras. Por tanto esta opción es falsa.

Opción b) Verdadera

Opción c) Falsa, L1 es un lenguaje y L2 otro distinto. Que L2 sea un subconjunto de L1 no significa necesariamente que los lenguajes sean del mismo tipo (de hecho no lo son).

Opción d) Es falsa, L2 puede ser reconocida por un autómata finito.

PREGUNTA: ¿Cuál de los siguientes autómatas tienen mayor capacidad de representación?:

a) Los autómatas finitos no deterministas.

b) Los autómatas finitos deterministas.

c) Todos los autómatas anteriores tienen la misma capacidad de representación.



RESPUESTA: la opción correcta es la c).

Los autómatas finitos no deterministas pueden transformarse en autómatas finitos deterministas siguiendo una serie de pasos, luego ambos tienen igual capacidad de representación o reconocimiento de lenguajes.