Exámenes resueltos Autómatas, gramáticas y lenguajes UNED Ingeniería Informática

[nosferacento]

PREGUNTA: Considere la gramática de símbolos terminales {(, ), ; , 1,2, 3}, símbolos no terminales {S, A, E} y producciones:

S --> (A)
A --> A;E | E
E --> 1 | 2 | 3 | S

La gramática genera listas de elementos que son números o a su vez listas separadas por el símbolo ";". Indicar cuál de las siguientes afirmaciones es verdadera:

a) El lenguaje es regular

b) El lenguaje es independiente del contexto no regular

c) No existe una gramática equivalente en Forma Normal de Chomsky









RESPUESTA: la opción correcta es la b)

Estudiamos la gramática propuesta y tratamos de ver qué cadenas genera:
Si en S --> (A) sustituimos A podemos tener:
(A;E) y a su vez ((A);E) y a su vez (((A));E) … que nos lleva a una salida de tipo (((1));2)

Por tanto podemos generar (numero;numero), ((numero);numero), (((numero));numero) … etc.

Tenemos que fijarnos en una cosa: los paréntesis están balanceados, es decir, por cada paréntesis de apertura tiene que haber un paréntesis de cierre.

Podemos intentar describir una expresión regular, pero nos vamos a encontrar con que no nos es posible hacer que los paréntesis se balanceen. Por ejemplo (usamos corchetes para indicar agrupación y diferenciarlo del carácter paréntesis):

[(numero;numero)] | [ ( [(numero)]+;numero) ]

Nos llevaría a cadenas como ((3)(1);2) donde se generan paréntesis balanceados pero insertando siempre un número con paréntesis detrás de otro.

Para balancear paréntesis como hace la gramática necesitamos contar, y la máquina más básica con capacidad para contar es un autómata a pila, ya que los autómatas finitos (lenguajes regulares) no tienen capacidad para contar. Por tanto la opción a) es falsa, no es un lenguaje regular.

Con un autómata a pila podemos generar este lenguaje, por tanto es un lenguaje independiente del contexto no regular. Provisionalmente vamos a responder la b), pero antes examinemos la opción c).

Si el lenguaje contiene la cadena vacía ε no existirá gramática equivalente en forma normal de Chomsky (FNC) sino una gramática en forma normal de Chomsky que genera L – { ε }, por tanto una cuestión a estudiar es si la gramática contiene la cadena vacía. Ya a primera vista podemos responder que no, la gramática no contiene la cadena vacía ya que la derivación inicial de S nos obliga a que la cadena más corta lleve como mínimo los paréntesis de apertura y cierre. Por tanto sí existe una gramática en FNC y podemos decir que la opción c) es falsa.

Respondemos por tanto la opción b)

[nosferacento]

PREGUNTA: Dada la siguiente expresión regular: (((a + b) c* (a + b)) + (( ac + ab) *))* y el siguiente autómata finito:

Indicar qué valores deben tener Etiqueta-1 y Etiqueta-2 para que el autómata acepte el mismo lenguaje que la expresión regular:

a) Etiqueta-1=a, b Etiqueta-2=a

b) Etiqueta-1=c Etiqueta-2=a

c) Etiqueta-1=a Etiqueta-2=a, b

d) Ninguna de las anteriores combinaciones es válida












RESPUESTA: la opción correcta es la c), aunque ver comentarios.

Nos dice que el autómata debe aceptar el mismo lenguaje, pero esto no deja claro si debe ser exactamente el mismo lenguaje, o podría reconocer un lenguaje más amplio que englobe el lenguaje de la expresión regular. Si se considerara oportuno, se podría incluir un comentario en el examen para indicar qué interpretación hemos hecho.

Nos fijamos primero en si la expresión regular admite ε, ya que el autómata admite ε por ser el estado inicial un estado de aceptación. Dado que el conjunto de la expresión regular está afectada por un asterisco de Kleene, efectivamente admite ε.

La expresión regular y el autómata no son fáciles de analizar con un simple vistazo, requiere un tiempo y posiblemente se pueda hacer de distintas maneras.

( ac + ab) * está contenido en la rama de abajo del autómata.

((a + b) c* (a + b)) está contenido en la rama de arriba del autómata.

Para ligar la rama de arriba con la de abajo necesitamos que etiqueta-1 sea a ya que la rama de abajo sólo admite comienzos por la letra a, mientras que para ligar la de abajo con la de arriba necesitamos que etiqueta-2 sea a,b ya que la rama de arriba admite inicios tanto con a como con b.

Otra forma de razonarlo: plantear cadenas que admite la expresión regular y ver qué valores de etiquetas se requerirían en el autómata:

La ER admite acccaac: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.

La ER admite acccaab: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.

La ER admite abacccb: no intervienen las etiquetas

La ER admite acbac: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.

La ER admite acbacbb: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 ha de ser Etiqueta-2=b.

Vemos que la Etiqueta-1 ha de ser a. La Etiqueta-2 tendría que ser b. Respondemos entonces la opción c). Esta pregunta tiene su complejidad, no permite de forma clara tener seguridad de que la conclusión a la que llegamos sea con certeza la correcta.

[nosferacento]

PREGUNTA: La estrella de Kleene o clausura de un lenguaje independiente de contexto, ¿es siempre un lenguaje independiente de contexto?

a) Sí, siempre

b) No, nunca

c) Depende de los casos









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

Para responder a esta pregunta tenemos que recordar lo siguiente. Los lenguajes independientes del contexto (LIC) son cerrados para la unión, concatenación, clausura o estrella de Kleene, clausura positiva (+), homomorfismo y reflexión. Es decir, la unión de dos LIC da por resultado un LIC, la concatenación de dos LIC da como resultado un LIC, la estrella de Kleene aplicada a un LIC da como resultado un LIC, etc.

Diferencia entre las propiedades de los LIC y de los lenguajes regulares: la intersección de dos lenguajes regulares es regular, pero la de dos LIC no tiene por qué ser un LIC.

Además el complementario de una expresión regular es regular, pero el complementario de un LIC no tiene por qué ser un LIC.

[nosferacento]

PREGUNTA: Indicar cuál de los siguientes lenguajes NO es regular:

a) L = {w ∈ {a, b}* | abab es subcadena de w}


b) L = {w ∈ {a, b}* | w ∉ {aⁿbⁿ} : n > 0}


c) El lenguaje consistente en las cadenas de caracteres tales que dos a's están separadas por 4i símbolos para algún entero i >= 0









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

Recordar que lenguaje no regular es el que:

a) No cumple el lema de bombeo para lenguajes regulares
b) No puede ser representado con un autómata finito
c) Necesita una pila o cinta para “recordar”

El lenguaje de la opción a) podemos expresarlo como (a+b)*abab(a+b)* y resulta un lenguaje regular, o al menos lo parece.

El lenguaje de la opción b) requiere contar el número de a´s y comprobar que no es igual al número de b´s. Necesitamos la capacidad de contar, y no podemos basarnos en un número finito de posibilidades porque el número de a´s y b´s es ilimitado. Por tanto no se puede representar con un autómata finito y no es un lenguaje regular.

El lenguaje de la opción c) podría representarse con un autómata que admite cualquier carácter en su estado inicial q0, y cuando recibe una a se mueve a un estado q1, un carácter distinto de a lleva a q2, otro carácter distinto de a mueve a q3 y con el siguiente carácter distinto de a mueve a q4. Para salir de q4 si el carácter recibido es distinto de a se vuelve a q0, y en caso de ser a se vuelve a q1

Serían estados de aceptación q0 (ya que se admite i=0)

No serían estados de aceptación q1, q2, q3, q4

Si es representable con un autómata finito el lenguaje es regular. La definición de este lenguaje no es del todo clara, pero parece que se adaptaría a la definición de lenguaje regular.

Respondemos por tanto la opción b).

[nosferacento]

PREGUNTA: Sea L el lenguaje generado por la siguiente gramática:

S -- > xxSyy | xy

Indicar cuál de las siguientes afirmaciones es verdadera:

a) L está formado por cualquier cadena que tenga el mismo número de x's que de y's.

b) L está formado por cualquier cadena que tenga el mismo número de x's que de y's, y que además tenga un número par de símbolos.

c) L está formado por cualquier cadena que tenga el mismo número par de x's y de y's.

d) Ninguna de las anteriores afirmaciones es verdadera.










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

La opción a) es falsa puesto que la gramática impone que las x´s han de venir antes que las y´s, por tanto cualquier cadena con el mismo número de x´s que de y´s no será válida. Por ejemplo yyxx no es válida.

La opción b) es falsa por el mismo motivo.

La opción c) es falsa por el mismo motivo, además el número de x´s o de y´s puede no ser par (aunque la cadena en su conjunto sí tenga un número de símbolos par.

Respondemos por tanto la opción d).

[nosferacento]

PREGUNTA: Indicar cuál es el autómata más sencillo (con menor capacidad de reconocimiento) que funcione de la siguiente manera. Dada cualquier cadena de x e y, substituya todas las x's por z's y devuelva una cadena con todas las y's al principio y las z's a continuación

a) Un autómata finito.

b) Un autómata a pila determinista.

c) Un autómata a pila no determinista.

d) Una máquina de Turing.









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

Dado que el autómata ha de devolver algo, necesitamos un autómata que pueda devolver un resultado. Esto tendría que hacerse a través de una pila donde quede reflejado el resultado, o a través de una cinta de una máquina de Turing. Por tanto descartamos la opción a) Un autómata finito ya que estos autómatas no pueden devolver (al  menos de forma explícita) un resultado.

Pensemos en un ejemplo. Si recibimos xyxyxxxyyy el autómata primero ha de leer todos los caracteres para sustituir las x´s por z´s, en este ejemplo zyzyzzzyyy. Después tiene que devolver una cadena con todas las y´s al principio y las z´s al final, en este ejemplo yyyyyzzzzz

Un autómata a pila puede introducir en la pila una z por cada x leída y una y por cada y leída. Una vez leída la cadena un autómata a pila no puede volver atrás, aunque sí podría realizar transiciones espontáneas sin consumir caracteres (leyendo la cadena vacía y modificando la pila). Pero pudiendo explorar sólo la cima de pila, no tendríamos forma de realizar una ordenación como la requerida (donde necesitaríamos poder enviar las y´s al final de la estructura de datos, pero una pila no nos permite hacer esto). Descartamos las opciones b) y c) por tanto.

Una máquina de Turing tiene la misma capacidad de computación que un computador y puede realizar esta tarea sin problema. Respondemos por tanto la opción d).

[nosferacento]

PREGUNTA: ¿Qué podemos afirmar del siguiente autómata?

a) Es un autómata no determinista que reconoce cadenas de x e y de tamaño mayor o igual a dos.

b) Está mal definido, ya que tiene dos estados de aceptación.

c) No tiene en cuenta la cantidad de símbolos z que se leen de la cadena de entrada.

d) Ninguna de las anteriores.












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

¿Es un autómata determinista o no determinista? Es un autómata determinista, puesto que no hay dos transiciones definidas para un mismo carácter de entrada. Por ello descartamos la opción a).

¿Está mal definido por tener dos estados de aceptación? No tiene por qué, un autómata puede tener ninguno, uno o más de un estados de aceptación.

¿Tiene en cuenta la cantidad de símbolos z que se leen de la cadena de entrada? El autómata puede llegar a aceptación con cero, uno o más de un símbolo z en la cadena de entrada. Por tanto la respuesta a la pregunta anterior es no.

La pregunta resulta un tanto confusa porque nos podemos preguntar si el autómata acepta la cadena zx y la respuesta es no, y esto pareciera dar a entender que sí se tiene en cuenta entonces la cantidad de símbolos z´s. Pero el autómata rechaza zx no porque tenga en cuenta el número de z´s en la cadena de entrada, sino porque la cadena no está contemplada como cadena del lenguaje definido.

[nosferacento]

PREGUNTA: Indique cuál de las siguientes afirmaciones es verdadera:

a) Dado un alfabeto Σ, para cualquier lenguaje construido sobre Σ existe una máquina de Turing que lo acepta

b) Dado un alfabeto Σ, cualquier lenguaje construido sobre Σ es recursivamente enumerable

c) Dado un alfabeto Σ, existen lenguajes construidos sobre Σ que no son recursivamente enumerable s y para los cuales no se puede construir una máquina de Turing que los acepte.









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

Las máquinas de Turing son las máquinas abstractas con mayor capacidad de reconocimiento de un lenguaje (y capacidades computacionales análogas a las de un computador) pero esto no significa que tengan capacidad para reconocer todos los lenguajes. De hecho, los lenguajes no reconocidos por máquinas de Turing se denominan lenguajes no recursivamente enumerables. La opción a) queda descartada.

De acuerdo con la explicación anterior la opción b) realmente es equivalente a la opción a) y por tanto la descartamos.

Respondemos por tanto la opción c).

[nosferacento]

PREGUNTA: Dado el lenguaje L generado por la siguiente gramática:

S -- >  xSy | xSyy | z

y el siguiente autómata (Nota: Se supone que la pila se encuentra inicialmente vacía. En el diagrama de transiciones algunos arcos tienen una etiqueta en la que el segundo elemento es ε. En estos casos se considera que el autómata ejecuta esta transición teniendo en cuenta únicamente el símbolo actual de la cadena de entrada sin inspeccionar el contenido de la cima de la pila. Por tanto, en estas transiciones no se extrae ningún elemento de la pila):

¿Qué función realiza la pila del autómata en relación a las cadenas del lenguaje L?

a) Lleva la cuenta del número de x's presentes en las cadenas del lenguaje L.

b) Lleva la cuenta del número de y's presentes en las cadenas del lenguaje L.

c) Lleva la cuenta del número de z's presentes en las cadenas del lenguaje L.

d) Lleva la cuenta del número de producciones necesarias para derivar las cadenas del lenguaje L.










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

Las cadenas del lenguaje L son

a) xzy, xxzyy, xxxzyyy, … es decir, un cierto número de x´s seguidas de una z y luego el mismo número de z´s que x´s hubieran aparecido previamente.
b) xzyy, xxzyyyy, xxxzyyyyyy … es decir, cierto número de x´s seguido de una z y a continuación el doble número de y´s que de x´s hubieran aparecido previamente.

c) z (cadena mínima admitida por la gramática)

El autómata de la figura es no determinista ya que tiene dos transiciones posibles para una misma entrada y símbolo en cima de pila.

Por la rama de q0-q1 no puede reconocer ninguna cadena de L, ya que tras recibir una x no tiene transición definida para la z, y si recibe una z no llega a aceptación.

Por la rama de q0-q2 la única cadena que puede reconocer es xzy. En este caso al leer la x pone una a en la pila y al leer la z pone otra a en la pila, dejando la pila con dos a´s. Dos a´s no son el número de x´s, de z´s ni de y´s de la cadena. Por tanto descartamos a), b) y c).

¿Cuáles son las producciones necesarias para derivar xyz?

1 S -- >  xSy
2 S -- > z

Se deriva xSy y de ahí xzy.

Por tanto la pila ha contado el número de producciones necesarias y respondemos la opción d).

Esta pregunta podemos calificarla de extraña, porque atribuirle un papel a la pila del autómata cuando éste sólo puede reconocer una cadena del lenguaje es un poco… extraño.

Otra forma de razonarlo: cada x implica una producción y cada z implica también una producción. El autómata apila una a con cada x ó cada z, por tanto está contando el número de producciones.

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {0, 1}, el lenguaje L se define como L = {w | w contiene un número par de 0's, o exactamente dos 1 's }. Indicar qué expresión regular genera el lenguaje L:

a) (1*01*01*0*) + (0*10*10*)

b) (1*01*01*)* + (0*10*10*)

c) (10101)* + (0*10*10*)











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

Analizamos la opción a). Nos permite generar 000 y esta cadena no contiene un número par de ceros ni exactamente dos unos, por lo que descartamos la opción a).

Analizamos la opción b). El sumando izquierdo implica que se admite la cadena vacía, que tiene cero 0´s. El número cero se considera par, por tanto se admite. El sumando izquierdo obliga a que el número de ceros sea siempre par si se escoge este sumando. El sumando derecho siempre tiene dos 1´s. Esta expresión regular genera un lenguaje como el indicado.

Analizamos la opción c). El sumando izquierdo implica que se admite la cadena vacía, que tiene cero 0´s. El número cero se considera par, por tanto se admite. En otro caso, el sumando izquierdo siempre tiene un número par de ceros. El sumando derecho es igual que el de la opción b, siempre tiene dos 1´s. 

Se podría responder la b) o la c), al menos los lenguajes que generan b) y c) cumplen con los criterios del lenguaje, ahora bien, ¿representan exactamente el lenguaje o a un subconjunto del lenguaje? Para responder esto nos ponemos cadenas mínimas del lenguaje y nos preguntamos qué opción permite generarlas:

Cadena vacía: la generan la opción b) y c).

Cadena 11: la generan la opción b) y c).

Cadena 00: la genera b) pero no la genera c). Por tanto b) representa el lenguaje mientras que c) representa un subconjunto del lenguaje.

Nota: pregunta sutil, hemos de responderla analizando detenidamente las expresiones y recurriendo a cadenas de prueba.

[nosferacento]

Con las últimas diez preguntas hemos completado un examen, que normalmente consta de diez preguntas tipo test. Es conveniente que se trate de resolver el examen haciendo una simulación de examen real, controlando el tiempo empleado y respondiendo todas las preguntas a la vez sin consultar ningún tipo de documentación, y luego comprobar cómo nos hubiera ido en ese caso supuesto "real" y qué nota habríamos sacado. Para quien quiera intentarlo, dejo el examen con enunciados completos en el archivo adjunto a este post (archivo jun_11_2a_sem_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...

[nosferacento]

Animo a todos los que estén estudiando! Cualquier sugerencia sobre temas de preguntas de examen me pueden escribir por foro o por MP. Sl2

[lore_Na]

Buenas, está súper bien tu aportación de este tema, muchas gracias. Tengo una pregunta que me hicieron en un examen de Teoría de la Computación que me ronda por la cabeza y no soy capaz de contestarla bien, si fueras tan amable de ayudarme...tengo el examen en pocos días y por si pregunta algo similar, me ayudaría un montón. Allí va la pregunta ¿Es posible diseñar un autómata a pila que reconozca un lenguaje de tipo 3? ¿Por qué?
Gracias de antemano.
Un saludo.

[nosferacento]

Hola, si por lenguaje tipo 3 entendemos el tipo 3 que define la jerarquía de Chomsky (https://es.wikipedia.org/wiki/Jerarqu%C3%ADa_de_Chomsky) la respuesta es que sí.

¿Por qué? Porque los lenguajes de tipo 3 en la jerarquía de Chomsky se corresponden con lenguajes regulares obtenibles mediante expresiones regulares. Estos lenguajes son un subconjunto de los lenguajes independientes del contexto que se definen con autómatas a pila.

Saludos

[jesus23482]

Buenos dias y felicitaciones por el trabajo realizado en este foro. Ha sido de gran utilidad para esta Asignatura de Automatas. Muy agradecido.
En relacion a la respuesta #94, mi duda es la siguiente:
¿por que no es posible que la etiqueta 2 sea ε, z; ε? entiendo que al hacer una transicion espontánea desde q1 a q2 consumiendo una z de la cima de la pila, lo que hace es garantizar que al llegar a q2, en la pila tengamos una z menos que las x's leidas, por lo cual aceptará en q2 tantas y's como z's y dara por buena toda cadena de tipo xn+1 yn.
Saludos y mil gracias.

[nosferacento]

Hola, tienes que comprobar que simultáneamente los valores de Etiqueta-1 y Etiqueta-2 permitan cumplir con lo que se quiere. Quizás uno de los dos valores es válido, pero ¿los dos al mismo tiempo lo son? Comprueba haber revisado esto... si encuentras que alguna de las opciones propuestas es válida explica cómo, con la respuesta que he dado yo en el mensaje correspondiente se indica que ni la a) ni la b) resultan válidas. Saludos

[nosferacento]

He actualizado algunas respuestas en base a comentarios que me han hecho llegar varias personas, gracias a todos por vuestra ayuda! (y en especial a klanderblzer)