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

PREGUNTA: Dada la siguiente gramática independiente del contexto G:

S  -- > aabS | baaS | abaS | aaSb | baSa | aSab | bSaa | aSba | Saab | Sbaa | Saba | abSa | ε

Indicar cuál de las siguientes afirmaciones es verdadera:

a) Las cadenas que genera G contienen el doble número de a's que de b's

b) Las cadenas que genera G tienen como mínimo una longitud de 2

c) En las cadenas que genera G todas las a's aparecen antes que las b's

d) Ninguna de las anteriores afirmaciones es verdadera












RESPUESTA: La opción correcta es la a), pero ver comentarios adjuntos.

Para ver si la opción a es correcta nos fijamos en cada una de las producciones. En todas ellas hay el doble de a´s que de b´s, excepto en la producción que nos lleva a la cadena vacía. El lenguaje incluye la cadena vacía. Esto nos puede generar duda: la cadena vacía contiene cero a´s y cero b´s. Si el número de b´s es cero, el doble de cero es cero. Por tanto podríamos entender que todas las cadenas del lenguaje contienen el doble de a´s que de b´s. Respondemos la opción a) aunque ciertamente es un tanto ambiguo el considerar que la cadena vacía contiene el doble de a´s que de b´s (es como decir que una persona tiene el doble de dinero que otra que no tiene dinero). Recomendaríamos escribir un comentario al respecto en el examen para aclarar cómo hemos interpretado la pregunta, de esta manera dejamos claro cuál ha sido nuestra interpretación lo que nos servirá en caso de que fuera necesario reclamar.

La opción b es falsa porque la gramática genera la cadena vacía cuya longitud es cero.

La opción c) es falsa porque hay producciones que derivan del símbolo inicial y comienzan por b, es decir, hay cadenas donde las b´s aparecen antes que las a´s.

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 sept11origA.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...

PREGUNTA: Dado el siguiente autómata a pila (Nota:se supone que inicialmente la pila se encuentra 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.)


Indicar cuál de las siguientes afirmaciones es FALSA:

a) El autómata a pila acepta las cadenas con el mismo número de x´s y de y's

b) El lenguaje que acepta el autómata a pila contiene al lenguaje {xⁿyⁿ: n >= 0}

c) El lenguaje que acepta el autómata a pila es independiente del contexto no regular

d) En las cadenas contenidas en el lenguaje aceptado por el autómata siempre deben aparecer las x 's antes que las y's










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

Tenemos que fijarnos en que nos piden indicar cuál opción es la falsa (no la verdadera, como suele ser habitual).

a, b; c significa: a el carácter de entrada, b lo que hay en la cima de pila y c lo que ponemos en la cima de pila.

x, ε; x significa que leemos x, y reemplazamos la cadena vacía en cima de pila por una x, lo que equivale a añadir una x a la pila.

x, y; ε significa que leemos x, y reemplazamos la y en cima de pila por una cadena vacía, lo que equivale a eliminar una y de la pila.

El autómata es no determinista, pero para llegar a aceptación ha de vaciarse su pila, lo que supone que:

Si lee una x tendrá que apilar x cuando no haya y´s en la cima de pila, y desapilar la y si existe en la cima de pila.

Si lee una y tendrá que apilar y cuando no haya x en la cima de pila, y desapilar la x si existe en la cima de pila.

Por tanto el autómata acepta las cadenas con el mismo número de x´s y de y's, la opción a) es verdadera.

El lenguaje aceptado es un superconjunto que contiene al lenguaje {xⁿyⁿ: n >= 0}. Téngase en cuenta que se admite la cadena vacía. Por tanto la opción b) es verdadera.

¿Es independiente del contexto no regular? Efectivamente, necesitamos contar por tanto no puede ser un lenguaje regular.

¿Deben aparecer antes las x´s que las y´s? No tiene por qué, pueden aparecer en cualquier orden, el único requisito es que haya el mismo número de x´s que de y´s. Por tanto la opción d) es falsa y respondemos la opción d).

PREGUNTA: Sea L1 el lenguaje compuesto por las cadenas formadas por subcadenas de 2 o más "x" seguidas de subcadenas de 2 o más "y", con un múmero indeterminado de "z" que pueden estar intercaladas tanto entre las "x" como entre las "y". Considere el autómata siguiente:


Indicar cuál de las siguientes afirmaciones es verdadera:

a) El autómata reconoce el lenguaje L1 , ya que no es necesario definir las transiciones correspondientes a los símbolos z´s

b) El lenguaje que reconoce el autómata es un subconjunto del lenguaje L1

c) El autómata no puede reconocer L1 porque es un lenguaje independiente del contexto










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


La opción a) es falsa: ante una transición no definida el autómata se parará y no llegará a aceptación.

El autómata reconoce xxx*yyy* que efectivamente es un subconjunto de un lenguaje más amplio que permite además de lo indicado intercalar z´s. Respondemos por tanto la opción b).

La opción c) es falsa porque el lenguaje L1 es regular.

PREGUNTA: Dada la siguiente gramática G:

S -- > zPzQz
Q -- > yQy
Q -- > zPz
Q -- > zPzPz
Q -- > ε
P -- > xPx
P -- > zQz
P -- > zQzQz
P -- > ε


Indicar cuál de las siguientes afirmaciones es verdadera:

a) Si se convierte G a una de sus posibles gramáticas en Forma Normal de Chomsky, el número de producciones resultante es mayor o igual que 34 y menor que 75

b) No existe una gramática en Forma Normal de Chomsky que genere el mismo lenguaje que G

c) En una de las posibles gramáticas en Forma Normal de Chomsky equivalente a G habrá una producción de la forma S -- > ZZZ donde Z es un nuevo no terminal no presente antes en G que deriva en el terminal z, esto es: Z -- > z

d) Ninguna de las anteriores afirmaciones es verdadera






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

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 tres z´s. Por tanto sí existe una gramática en FNC y podemos decir que la opción b) es falsa.

Una gramática se dice que está en forma normal de Chomsky si cumple  2 + 3 condiciones:

a) Toda producción es de tipo A -- > BC con A, B, C variables ó
b) o es de tipo A -- > a donde A es variable y a un símbolo terminal
c) Cumple no tener producciones ε ni producciones unitarias ni símbolos inútiles.

Para poner una gramática en FNC primero la liberamos de producciones ε , producciones unitarias y símbolos inútiles. Luego hemos de hacer lo siguiente:

a) Conseguir que todos los cuerpos de longitud 2 ó superior estén formados solo por variables (que no tengan símbolos terminales)

b) Descomponer los cuerpos de longitud 3 ó más variables en una serie de producciones, teniendo cada una de ellas un cuerpo formado por solo dos variables.

En una gramática en FNC para la gramática dada una producción como S -- > ZZZ no podría existir, ya que no cumple las normas para las gramáticas en FNC, en concreto un cuerpo no puede tener longitud 3 (tendría que descomponerse hasta longitud 2). Por tanto la opción c) es falsa. Tenemos ya b) y c) falsas.

Nos queda por decidir: ¿Será la opción a) verdadera o por el contrario será la d)? Ummmm... Resolver esto ¿requiere que pongamos la gramática en FNC y comprobemos el número de producciones…? No estamos seguros. Esto puede requerir bastante tiempo (que quizás no tengamos en el examen). Si tenemos tiempo podemos hacerlo:

Eliminamos las producciones ε y nos quedan 20 producciones:

1.   S -- > zPzQz
2.   S -- > zzQz
3.   S -- > zPzz
4.   S -- > zzz
5.   Q -- > yQy
6.   Q -- > yy
7.   Q -- > zPz
8.   Q -- > zz
9.   Q -- > zPzPz
10.   Q -- > zzPz
11.   Q -- > zPzz
12.   Q -- > zzz
13.   P -- > xPx
14.   P -- > xx
15.   P -- > zQz
16.   P -- > zz
17.   P -- > zQzQz
18.   P -- > zzQz
19.   P -- > zQzz
20.   P -- > zzz

No tenemos producciones unitarias tipo A -- > B con lo cual no hay que eliminar producciones unitarias.
No tenemos símbolos inútiles con lo cual no hay que eliminar símbolos inútiles.
Hacemos cambio de terminales por variables y nos quedan 23 producciones:

1.   M -- > z
2.   N -- > x
3.   T -- > y
4.   S -- > MPMQM
5.   S -- > MMQM
6.   S -- > MPMM
7.   S -- > MMM
8.   Q -- > TQT
9.   Q -- > TT
10.   Q -- > MPM
11.   Q -- > MM
12.   Q -- > MPMPM
13.   Q -- > MMPM
14.   Q -- > MPMM
15.   Q -- > MMM
16.   P -- > NPN
17.   P -- > NN
18.   P -- > MQM
19.   P -- > MM
20.   P -- > MQMQM
21.   P -- > MMQM
22.   P -- > MQMM
23.   P -- > MMM


Las producciones de longitud 3 o superior las tenemos que desagregar en producciones de longitud 2, para ello añadimos 11 producciones adicionales y hacer el reemplazo en las 23 anteriores, resultando un total de 34 producciones:

A -- > MP
B -- > MQ
C -- > AB
D -- > MM
E -- > QM
F -- > TQ
G -- > AA
H -- > PM
I -- > NP
J -- > MQ
K -- > JJ

En definitiva, quizás el proceso seguido no sea el único y quizás se pueda hacer de otra manera, pero vemos que podemos llegar a una gramática en FNC donde para una de sus posibles gramáticas en Forma Normal de Chomsky, el número de producciones resultante es mayor o igual que 34 y menor que 75.

Pregunta larga de responder y para la que quizás se pueda responder la opción a) sin necesidad de hacer el desarrollo… de todas formas ahí queda para quien le interese como ejercicio.

PREGUNTA: Sea L el lenguaje que reconoce el siguiente autómata finito


Indicar cuál de las siguientes gramáticas regulares genera el mismo lenguaje:

a)
S -- > bS | aA
A -- > aA | bB
B -- > bS | ε

b)
S -- > bS | aS | aA | ε
A -- > aA
B -- > bS | ε

c)
S -- > bS | aA | ε
A -- > aA | Bb
B -- > bS | ε


d) Ninguna de las anteriores gramáticas genera L






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

Si identificamos el estado qo con S, el estado q1 con A, el estado q2 con B y tenemos en cuenta que q3 al no ser de aceptación y no permitir el retorno a un estado de aceptación puede ser ignorado tenemos que:

La opción a) parece permitir todas las transiciones necesarias pero no admite la cadena vacía (que el estado inicial sea de aceptación), por tanto no genera L.

La opción b) no genera L porque permitiría salir del estado inicial y volver a él con una a, cosa que no es posible con el autómata.

La opción c) permite todas las transiciones necesarias y admite la cadena vacía.

Respondemos por tanto la opción c).

PREGUNTA: Decidir si es verdadera o falsa la siguiente afirmación: "Dado un lenguaje regular L, existe una gramática independiente de contexto en forma normal de Chomsky que genera el mismo lenguaje."

a) Siempre

b) Nunca

c) Depende de L










RESPUESTA: la opción correcta es la c)

Razonamiento: si L es un lenguaje regular se puede expresar como Gramática Independiente del Contexto (GIC) ya que los lenguajes regulares son LIC. No obstante, si el lenguaje contiene la cadena vacía ε no existirá gramática equivalente en forma normal de Chomsky sino una gramática que genera L – { ε } Respondemos por tanto la opción c), depende del lenguaje.

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

S -- > A1B
A -- > 0A | ε
B -- > 0B | 1B | ε

Indicar cuál de las siguientes afirmaciones es verdadera:

a) L es independiente del contexto no regular

b) L contiene la cadena vacía

c) Sea w la cadena de menor longitud de L, entonces |w| = 2

d) L es regular y puede expresarse mediante la expresión regular 0*1(0 + 1)*









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

Analizamos la opción a). La expresión regular 0*1(0 + 1)* representa el lenguaje, por tanto a) es falsa.

Analizamos la opción b). S deriva a A1B, con lo cual siempre contendrá un 1, por tanto el lenguaje no contiene la cadena vacía.

Analizamos la opción c). 1 pertenece al lenguaje, por tanto la cadena con menor longitud tiene cardinalidad 1 y no 2, por tanto la opción c) es falsa.

Analizamos la opción d). El lenguaje puede contener ninguno, uno o muchos ceros iniciales. A continuación viene un 1, y seguidamente puede contener indistintamente ningún símbolo o cualquier cantidad de ceros y unos indistintamente. Esto lo representa bien la expresión regular, por tanto respondemos la opción d).

Nota: si nos preguntara ¿es esta gramática regular? La respuesta sería no, porque para una gramática ser regular debe cumplir:

- En el lado izquierdo de las reglas solo puede haber un único símbolo no terminal
- En el lado derecho puede aparecer: un símbolo terminal, un símbolo terminal seguido de un no terminal ó el símbolo de cadena vacía. La producción S - > A1B no cumple con estas normas, por tanto la gramática no es regular.

Sin embargo, el hecho de que una gramática no sea regular no obligatoriamente implica que no genere un lenguaje regular, de hecho en este caso la gramática no es regular y sin embargo genera un lenguaje regular.

PREGUNTA:  Indicar cuál de las siguientes igualdades entre expresiones regulares es verdadera:

a) a(a + ba)* = (a + ab)*a

b) a(a + ba)* = aa*b*a

c) a(a + ba)* = aa* (ba)*









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

Empezamos analizando la opción a) y en concreto su lado izquierdo. Las cadenas que admite son a, aa, aaa… y aba, ababa, abababa… y aaba, aaaba, aaaaba… y ababababaaaa… obliga a que la cadena empiece con a y  termine con a.

La opción a) lado derecho admite a, aa, aaa… y aba, ababa, abababa y aaba, aaaaba, aaaaba… y ababababaaaa… obliga a que la cadena comience con a y termine con a.

La opción a) parece correcta, de todas formas vamos a revisar las otras opciones.

La opción b) lado izquierdo admite a, mientras que la opción b) lado derecho no admite a, por tanto b) es falsa.

La opción c) lado izquierdo obliga a comenzar con a y terminar con a, al igual que esta opción en el lado derecho. Pero si nos fijamos en el lado izquierdo tenemos el símbolo + y en el lado derecho no. El lado izquierdo permite abaaaaaaa ¿lo permite el lado derecho?

La opción c) lado derecho no permite abaaaaaaa porque si se introduce una b, obligatoriamente ha de ir seguida de una sola a (no existe el +, símbolo de opción y no podemos introducir varias a´s despué de una b). Por tanto la opción c) es falsa.

Hay distintas formas de razonar para llegar a la respuesta, da igual cuál utilicemos siempre que hagamos un razonamiento correcto.

PREGUNTA: Indicar cuál es el tipo de autómata más sencillo (menor capacidad de reconocimiento) capaz de reconocer el lenguaje {xⁿy^mzⁿ | n >=25, m>=50 }

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 b).

Necesitamos contar las apariciones de x y z para comprobar que haya más de 25 apariciones, y las de y para comprobar que haya más de 50 apariciones. A primera vista podría pensarse que al necesitar contar un autómata finito no sería válido, pero realmente tenemos que considerarlo con cuidado. Vamos a rechazar la opción del autómata finito porque hemos de verificar que el número de x sea igual al número de z´s y un autómata finito no puede guardar memoria del número de apariciones de un carácter. Tener en cuenta que si se tratara sólo de verificar si aparecen 25 x´s o más de 25 x´s esto sí lo puede hacer un autómata finito.

Con un autómata a pila determinista podríamos poner una x en la pila con cada x que nos venga. Al recibir una y, podríamos tener 50 transiciones en las que solo se admiten y´s y no se coloca nada en la pila (esto haría al autómata muy grande, pero no hay nada que lo prohiba). Finalmente al recibir una z empezamos a desapilar x´s, pasando a aceptación con una transición que no consume carácter alguno que se produce cuando en cabeza de pila tenemos la señal de fondo de pila. ¿Qué ocurre si recibimos una cadena con más z´s que x´s? ¿Podríamos pensar que se llega al estado de aceptación al usarse la transición con la cadena vacía y que realmente el comportamiento corresponde al de un autómata no determinista que acepta tanto el lenguaje propuesto como lenguajes donde el número de z´s sea simplemente mayor o igual que el de x? No, el motivo para ello es la definición de aceptación por estado final en un autómata a pila: “Para que una cadena sea aceptada por un autómata a pila que acepta por estado final tienen que cumplirse dos condiciones: a) Que la cadena se consuma totalmente y b) Que el autómata una vez consume la cadena quede en un estado de aceptación (sin importarnos el contenido de la pila).

En este caso si recibimos z´s adicionales no habría transición definida, por tanto la cadena no se puede consumir totalmente y al no haber consumo total de la cadena la cadena no es aceptada (ni aún suponiendo que se produjera la transición espontánea final).