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

[nosferacento]

PREGUNTA:  Sea L el lenguaje definido por el conjunto de cadenas del alfabeto Σ   = {a, b, c} que contienen al menos una a y al menos una b. Indicar cuál de las siguientes afirmaciones es VERDADERA:

a) L es un lenguaje independiente del contexto no regular

b) L es un lenguaje regular y por tanto, es posible encontrar una expresión regular que lo reconozca

c) La definición del lenguaje impone restricciones acerca del número de c's que deben contener las cadenas del lenguaje




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

Vamos a tratar de plantear un autómata finito que represente el lenguaje. Si lo logramos, ya sabremos que es una expresión regular.

Partimos de un estado inicial q0. Si en dicho estado se lee una c, el autómata se mantiene en q0. Si se lee una a el autómata pasa al estado q1 y si se lee una b el autómata pasa al estado q2. Si estando en q1 se lee una c ó una a, el autómata permanece en q1, mientras que si se lee una b el autómata pasa al estado de aceptación q3. Si estando en q2 el autómata lee una b ó una c, el autómata permanece en q2, mientras que si lee una a pasa al estado de aceptación q3. En q3 la lectura de a, b ó c hacen que se permanezca en q3.

Si queremos estar más seguros lo dibujamos y lo probamos con diferentes cadenas.

Analizamos las opciones: a) es falsa porque dice que es un lenguaje no regular.

b) es verdadera pues como hemos visto es un lenguaje regular.

c) es falsa porque la definición del lenguaje no dice nada acerca del número de c´s que deben contener las cadenas del lenguaje.

[nosferacento]

PREGUNTA: Dada la siguiente gramática, donde A es el símbolo inicial de la gramática:

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

Indicar cuál de las siguientes afirmaciones es VERDADERA:

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

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

c) La gramática genera un lenguaje con un número finito de cadenas

d) Ninguna de las anteriores afirmaciones es verdadera




RESPUESTA: la opción correcta es la a)

Tenemos que prestar atención a cuál es el símbolo inicial de la gramática, normalmente S pero en este caso nos indican específicamente que es A. Por ello vamos a reescribir la gramática comenzando con la regla asociada al no terminal A para evitar confundirnos.

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

Al analizar la gramática con A como símbolo inicial vemos que B y S son símbolos inalcanzables, por tanto la gramática se reduce a esta regla: A -- > 0A | λ

Esta gramática es recursiva por la derecha y admite la cadena vacía λ dentro del lenguaje que genera. El lenguaje generado es λ, 0, 00, 000, 0000… que es lo mismo que la expresión regular 0*

Analizamos las posibles respuestas:
a) es verdadera
b) es falso, el símbolo 1 no aparece dentro del lenguaje
c) es falso, el número de cadenas que genera es infinito
d) es falso

Pregunta sencilla pero donde mucha gente cometerá la equivocación de usar S como símbolo inicial de la gramática. ¡Prestar atención!

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

[nosferacento]

PREGUNTA: Sea el lenguaje L = {xⁿy^mzⁿ : con n y m > 0, y con n ≠ m}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?

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

El lenguaje implica que el número de x´s ha de ser igual al número de z´s, y con al menos una y entre las x´s y las z´s. El número de x´s y z´s tiene que ser distinto al número de y´s. El número mínimo de cualquier símbolo es 1.

Con estas premisas xyz no se acepta porque el número de y´s tiene que ser distinto que el número de x´s y de z´s. Se aceptarían las siguientes cadenas:

xyyz, xyyyz, xyyyyyy…yyyyyyz, xxyzz, xxxyzzz, xx…xxyzz..zz, xxxyyzzz, etc.

Necesitamos contar, con lo cual ya sabemos que los autómatas finitos no podrán representar este lenguaje.

Ahora nos preguntamos, ¿podrá un autómata a pila reconocer este lenguaje? Necesitamos comprobar las siguientes restricciones:

a)   Que el número de z´s sea distinto al número de x
b)   Que el número de x´s sea igual al número de z´s
c)   Que tanto el número de x´s como de y´s sea al menos 1

Con un autómata a pila podemos contar algo añadiendo a la pila y comprobar la coincidencia con otra cosa desapilando, pero aquí esto no es suficiente, necesitaríamos contar dos cosas: las x´s y las y´s, luego desapilar con las z´s y verificar que las x´s están en distinto número que las y´s. Esta capacidad de computación podríamos decir que necesita “2 pilas” y está por encima de las posibilidades de un autómata a pila, sea determinista o no determinista, por lo que concluimos que la máquina más simple para reconocer este lenguaje ha de ser una máquina de Turing.

Otra vía para tratar de responder esta pregunta es usar el lema de bombeo para lenguajes independientes del contexto. El lenguaje xⁿy²ⁿzⁿ sería un subconjunto del lenguaje y por tanto debería ser un LIC si el lenguaje propuesto fuera un LIC. Supongamos que este lenguaje es un LIC. Entonces existe un valor constante n de forma que para z = xⁿy²ⁿzⁿ  se cumpliría que:

z = uvwxy
|vwx| <= n
v ≠ λ, x ≠  λ
   
Si |vwx| <= n significa que vwx ha de estar formado en nuestro caso por símbolos y´s, mientras que x ha de contener símbolos x´s y posiblemente y´s , y z ha de estar formado posiblemente por símbolos y´s y por símbolos z´s.

Según el lema de bombeo uvkwxky ha de pertenecer al lenguaje para todo k>=0, pero si hacemos k=0 tenemos que la parte central de la cadena estaría formada por como mucho n símbolos y, mientras que necesitamos 2n símbolos y. La cadena no pertenecería al lenguaje y no se cumple el lema de bombeo para lenguajes LIC, por lo que podemos concluir que el lenguaje no es un LIC.

Conclusión: será necesaria una máquina de Turing para reconocer el lenguaje.

Esta pregunta es menos simple de lo que parece.

[nosferacento]

PREGUNTA: El lema del bombeo aplicado a los lenguajes regulares nos demuestra que para todo autómata finito no determinista existe un autómata finito determinista que reconoce el mismo lenguaje.

a) Verdadero.
b) Falso.



RESPUESTA: la opción correcta es la b). El lema de bombeo aplicado a los lenguajes regulares nos demuestra que si un lenguaje no cumple el lema de bombeo no es un lenguaje regular. En caso de cumplirse, no es garantía de que el lenguaje sea regular ni de que no lo sea. No tiene nada que ver con lo que indica el enunciado de la pregunta, por lo tanto la respuesta es la b), Falso.

[nosferacento]

PREGUNTA: Dado el lenguaje L = {xⁿy^m : n, m > 0} definido por la gramática

S -- > xX
X -- > xX
X -- > yY
Y -- > yY
Y -- > λ

¿Podríamos construir su forma normal de Chomsky?

a) Si.
b) No.





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

Recordar que la FNC implica estas condiciones:

a)   El lenguaje no genera la cadena vacía
b)   Toda producción es de tipo A -- > BC ó A -- > a
c)   La gramática no tiene producciones λ ni producciones unitarias ni símbolos inútiles.

¿Genera este lenguaje la cadena vacía? S ha de derivar en xX. Dado que X ha de derivar en xX ó yY llegamos a xxX ó xyY. Si derivamos Y a la cadena vacía tenemos que la cadena más corta que se puede generar es xy. Por tanto el lenguaje no contiene la cadena vacía.

Nota: puede despistar el que haya una producción que lleve a la cadena vacía, pero esto no significa que el lenguaje genere la cadena vacía.

Vamos a intentar ponerla en forma normal de Chomsky. Para ello en primer lugar eliminamos las producciones λ. Reemplazamos las producciones λ haciendo el reemplazo por todas las producciones alternativas posibles. La gramática queda:

S -- > xX
X -- > xX
X -- > y
Y -- > yY
Y -- > y

En segundo lugar eliminaríamos producciones unitarias tipo A -- > B pero como no tenemos pasamos al siguiente paso.

En tercer lugar eliminaríamos símbolos inútiles pero como no tenemos pasamos al siguiente paso.

Nos falta dejar la gramática en la forma adecuada. Para ello introducimos variables adicionales como F -- > x así como G -- > y. La gramática queda:

S -- > FX
X -- > FX
F -- > x
X -- > y
Y -- > GY
Y -- > y
G -- > y

Esta gramática está en forma normal de Chomsky y genera el mismo lenguaje que la gramática inicial, por tanto la respuesta es la a), sí se puede construir la FNC.

[nosferacento]

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

S -- > xX
S -- > Sy
S -- > xy

L es reconocido por el siguiente automáta a pila:

Podemos asegurar que el lenguaje es un lenguaje independiente del contexto no regular

a) Verdadero.
b) Falso.




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

Veamos cadenas que genera el lenguaje: no se admite la cadena vacía. Genera: xy, xxy, xxxy, xxx…xxxy, xyy, xyyy, xyyy…yyy, xxx…xxxxyyyy…yyy

El lenguaje permite tantas x antes y tantas y después como se quiera, obligando a que aparezca una xy central.

Vamos a tratar de encontrar una expresión regular que describa el lenguaje: x*(xy)y* permite que haya tantas x antecesoras como se quiera, obliga a que haya una xy central y permite tantas y posteriores como se quiera. También podemos escribir el lenguaje como xx*yy*. Además si nos fijamos en el autómata a pila propuesto, podemos transformarlo en un autómata finito determinista que parte de qo y pasa a q1 cuando recibe una x, admite tantas x como se desee en q1 mediante un lazo y pasa a q2 (aceptación) al recibir una y. Además en q2 admite tantas y como se desee mediante un lazo.

Por tanto se trata de un lenguaje regular, con lo cual es falso que sea un lenguaje independiente del contexto no regular. Respondemos la opción b).

Nota: el hecho de que el lenguaje se describa con un autómata a pila tal y como se plantea en el enunciado significa que es un LIC, pero no dice nada respecto de si el lenguaje es regular o no regular ya que los lenguajes regulares son un subconjunto de los LIC.

[nosferacento]

PREGUNTA: Dado el lenguaje L₁ = {xⁿyⁿ : n > 0} y el lenguaje L₂ = {xⁿy²ⁿ : n > 0}.

a) El lenguaje L = L1 ∩ L2 no es reconocido por un autómata finito.

b) El lenguaje L = L1 ∩ L2 no es reconocido por un autómata a pila determinista.

c) El lenguaje L = L1 ∩ L2 no es reconocido por un autómata a pila no determinista.

d) Ninguna de las anteriores






RESPUESTA: la opción correcta es la d)

el lenguaje L1 comprende las cadenas: xy, xxyy, xxxyyy … siendo reconocible por un autómata a pila al que le basta apilar x´s y desapilarlas con y´s hasta vaciar la pila.

El lenguaje L2 comprende las cadenas xyy, xxyyyy, xxxyyyyyy … siendo reconocible por un autómata a pila al que le basta apilar dos x´s cada vez que reciba una x y desapilar una x cada vez que reciba una y hasta vaciar la pila.

Por tanto, L1 y L2 son lenguajes independientes del contexto. Ahora nos preguntan acerca de la intersección de estos dos lenguajes, es decir, el lenguaje que representa las cadenas comunes entre ambos. Sin embargo, ambos lenguajes no tienen cadenas en común (prueba a buscar alguna y verás que no hay), con lo que el lenguaje intersección es el lenguaje vacío. El lenguaje vacío es reconocido por cualquier autómata que simplemente tiene un estado de aceptación y no tiene transiciones. Por tanto, sí es reconocido por un autómata finito, a pila determinista o a pila no determinista, lo que hace las respuestas a), b) y c) falsas. Respondemos por tanto la opción d).

[nosferacento]

PREGUNTA:  ¿Es posible construir la forma normal de Chomsky de la gramática siguiente?

S -- > AB
A -- > aAc
A -- > λ
B -- > bBc
B -- > λ
 
a) Si.

b) No.





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

El símbolo inicial, dado que no nos indican otra cosa, es S. Con la producción S -- > AB podemos alcanzar la cadena vacía, ya que A deriva a la cadena vacía y B deriva a la cadena vacía. Por tanto, la cadena vacía forma parte del lenguaje generado por la gramática.

Recordar que la FNC implica estas condiciones:

a)   El lenguaje no genera la cadena vacía
b)   Toda producción es de tipo A -- > BC ó A -- > a
c)   La gramática no tiene producciones λ ni producciones unitarias ni símbolos inútiles.

En este caso el lenguaje genera la cadena vacía por lo que respondemos la opción b), no es posible generar la forma normal de chomsky de esta gramática.

Nota: si se nos preguntara, ¿es posible generar una gramática que genere un lenguaje igual al lenguaje de esta gramática, excluida la cadena vacía, en forma normal de chomsky? La respuesta sería que podríamos responder que sí siguiendo el siguiente proceso (indicado a continuación PARA QUIEN LE INTERESE HACERLO COMO EJERCICIO). Primero, eliminar las producciones que llevan a la cadena vacía:

S -- > AB
S -- > A
S -- > B
A -- > aAc
A -- > ac
B -- > bBc
B -- > bc

Segundo, eliminar las producciones unitarias. Para ello se utiliza el método de pares unitarios:

(S, S) | (S, A) | (S, B)
(A, A)
(B, B)
S -- > AB | aAc | ac | bBc | bc
A -- > aAc | ac
B -- > bBc | bc

Hacemos estos cambios: X -- > a, Y -- > b, Z -- > c     con lo que la gramática queda:

S -- >  AB | XAZ | XZ | YBZ | YZ
A -- > XAZ | XZ
B -- > YBZ | YZ

Nos faltaría transformar las producciones que contienen tres no terminales en producciones con 2 no terminales. Para ello hacemos T -- > AZ,  M -- > BZ y la gramática queda:

S -- >  AB | XT | XZ | YM | YZ
A -- > XT | XZ
B -- > YM | YZ
T -- > AZ
M -- > BZ

Que ya está en forma normal de chomsky y representa el lenguaje inicial excepto la cadena vacía, es decir, L – { λ }

[nosferacento]

PREGUNTA: Sea el lenguaje L = {xⁿy^mzⁿ : con n > 0 y m par}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?

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

Planteamos en primer lugar ejemplos de cadenas que pertenecen al lenguaje. El lenguaje no admite la cadena vacía. Admite xyyz, xyyyyz, xyy..yyz, x…xyy…yyz…z. Al hacer la referencia m par podemos preguntarnos si el 0 es considerado par. Vamos a considerar que sí. El cero cumple con la definición de número par: es un entero múltiplo del dos, 0 × 2 = 0. Entonces la cadena xz también sería admitida, así como xxyy, xxxyyy, etc.

Para reconocer este lenguaje podríamos apilar x´s y desapilar y´s, lo cual puede ser realizado por un autómata a pila. Sin embargo, adicionalmente necesitamos verificar que el número de y´s sea par. Esto podríamos hacerlo con un autómata a pila que apila con cada y que recibe y desapila con la siguiente. Vamos a tratar de representar el autómata. Primero lo dibujamos de forma aproximada y luego lo vamos perfeccionando a medida que vamos haciendo pruebas.

Para permitir la posibilidad de que vengan y´s o no vengan y´s podríamos pensar en usar no determinismo (transiciones basadas en la cadena vacía, “espontáneas”), pero tenemos que estudiar si podemos evitar el no determinismo. Vamos a intentarlo, puesto que la máquina determinista es más simple que la no determinista.

Ahora le pasamos las cadenas al autómata y comprobamos el comportamiento:

xz:  acepta
xxzz: acepta
xx…xxzz…zz: acepta
xyyz: acepta
xyyyyz: acepta
xxyyzz: acepta

Conclusión: podemos reconocer el lenguaje con un autómata a pila determinista y la respuesta correcta es la b).

Nota: la posibilidad de un autómata finito la descartamos desde el momento en que necesitamos contar para reconocer el lenguaje.

Nota: este ejercicio quizás se pueda resolver de forma intuitiva teniendo en cuenta que las x´s se pueden contrarrestar con las z´s y que las y´s al ser pares se pueden contrarestar a sí mismas. No obstante, consideramos preferible representar el autómata y hacer comprobaciones antes que basarnos en una visión rápida.

[nosferacento]

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

S -- > AB
A -- > aAc
A -- > λ
B -- > bBc
B -- > λ

¿Cuál es la máquina más simple que puede reconocer este lenguaje?

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

Analicemos qué cadenas genera la gramática.

El símbolo inicial, dado que no nos indican otra cosa, es S. Con la producción S -- > AB podemos alcanzar la cadena vacía, ya que A deriva a la cadena vacía y B deriva a la cadena vacía. Por tanto, la cadena vacía forma parte del lenguaje generado por la gramática.

Las producciones A nos permiten generar cadenas con el mismo número de a´s que de c´s, por ejemplo ac, aacc, aaaccc, etc.

Las producciones B nos permiten generar cadenas con el mismo número de b´s que de c´s, por ejemplo bc, bbcc, bbbccc, etc.

La producción AB permite que se puedan concatenar cero o muchos pares de (ac) con cero o muchos pares de (bc).

Vamos a tratar de escribir una expresión regular que represente el lenguaje:

(ac)*(bc)*

¿Esta expresión regular representa el lenguaje? (incluido la cadena vacía). La respuesta es que no, esta expresión regular permite cadenas como ac, acac, acacac … ó bc, bcbc, bcbcbc… o la concatenación de ambas, pero esto no es el lenguaje que queremos representar.

Si nos fijamos necesitamos contar el número de a´s y verificar que el número de c´s que vengan a continuación sea igual, ó contar el número de b´s y verificar que el número de c´s que venga a continuación sea igual. Si necesitamos contar vamos a necesitar al menos un autómata a pila. Vamos a tratar de construir un autómata a pila que reconozca el lenguaje.

Podríamos pensar en este autómata, pero la transición λ desde q1 introduce no-determinismo.

Para hacerlo determinista eliminamos la transición con cadena vacía desde q1 y a cambio hacemos q0 estado de aceptación.

Con este autómata tenemos el problema de que obliga a recibir al menos ac una vez, mientras que el lenguaje permite que ac aparezca cero o muchas veces.

Vamos a corregir esto y redibujar el autómata:

Ahora parece que sí está correcto. Es un autómata a pila determinista. Le pasamos cadenas:

λ : acepta
ac: acepta
aacc: acepta
aaa…ccc… : acepta


Nota: el autómata ha resultado relativamente complejo debido a la cantidad de variantes que admite. ¿Podíamos haber respondido sin dibujar el autómata? Posiblemente sí, teniendo en cuenta que el autómata “simplemente” tiene que apilar y desapilar en dos etapas puede “intuirse” que es un autómata a pila determinista, pero esto depende de “la capacidad de visión” que tenga cada uno. Esta pregunta es menos sencilla de lo que parece...

[nosferacento]

PREGUNTA: Dado el lenguaje L = {xⁿyⁿz^m : donde se cumplen las siguientes condiciones, n > 0, si n es par m es igual a 2 o si n es impar m es igual a 3}

¿Cuál es la máquina más simple que puede reconocerlo?

a) Un autómata finito

b) Un autómata a pila determinista

c) Un autómata a pila no determinista

d) Ninguna de las anteriores






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

Veamos algunas de las cadenas que reconoce el lenguaje:

Con n=1, n es impar, reconoce xyzzz
Con n=2, n es par, reconoce xxyyzz
Con n=3, n es impar, reconoce xxxyyyzzz
Con n=4, n es par, reconoce xxxxyyyyzz
Con n=5, n es impar, reconoce xxxxxyyyyyzzz

Necesitamos contar las apariciones de las x´s para luego comprobar que las apariciones de las y´s sean coincidentes en número. Desde el momento en que necesitamos contar descartamos los autómatas finitos, requeriremos como mínimo un autómata a pila. En este caso, si logramos diferenciar cuándo el número de x´s es impar, sabemos que podemos llegar a aceptación desapilando las x´s y añadiendo dos z´s. Si logramos diferenciar cuándo el número de x´s es par, sabemos que podemos llegar a aceptación desapilando las x´s y añadiendo tres z´s.

Vamos a tratar de plantear un autómata a pila que resuelva el problema. A priori no tenemos del todo claro si va a ser posible resolverlo con un autómata a pila determinista o no. Después de varias pruebas y tanteos planteamos el siguiente autómata:

Este es un autómata a pila determinista. Pasamos las cadenas que habíamos planteado a este autómata. Vemos que las resuelve bien, y vemos que la generalización no plantea problemas. Hemos representado el lenguaje con un autómata a pila determinista, por tanto la opción correcta es la b).

Nota: el autómata resuelve bien porque logra diferenciar par / impar mediante transiciones y porque una vez detectado si el caso es par o impar tiene que añadir un número finito de símbolos.

Los estados se pueden interpretar de la siguiente manera:

q2: se ha reconocido un número impar de x´s
q3: se ha reconocido un número par de x´s
q6: se acepta la cadena de entrada

[nosferacento]

PREGUNTA. Sea el lenguaje L = {xⁿy^mzⁿ : con n y m > 0, y con n = m}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?


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

Al indicarnos que n = m el lenguaje es equivalente a xnynzn : con n > 0, es decir, cadenas con el mismo número de x´s, y´s y z´s que aparecen en este orden. Un autómata finito no puede recordar el número de x´s que han aparecido para compararlo con el número de y´s y el número de z´s. Con un autómata finito podríamos reconocer ciclos simples xyz pero no cadenas del tipo xxxyyyzzz donde necesitamos recordar los caracteres que han aparecido previamente. 

Pensemos ahora en un autómata a pila. Podríamos pensar en apilar con las x´s, luego desapilar con las y´s, pero ya no podríamos comprobar las z´s.

Supongamos ahora que apilamos dobles x´s cada vez que encontramos una x, luego hacemos una transición a otro estado al encontrar una y y desapilamos una x simple por cada y, luego hacemos una transición con una z a otro estado y desapilamos una x simple por cada z. Una cadena como xxyyzz nos llevaría a aceptación pero una cadena como xxyzzz también porque no sabemos al desapilar con las z´s quién ha puesto el símbolo, si se debe a una x ó se debe a una y.

Un autómata a pila no determinista nos permite explorar múltiples vías, pero tampoco nos permite recordar la información que necesitamos recordar.

Una máquina de Turing con varias cintas puede almacenar la información que desee (y puede reducirse a una máquina de Turing de una cinta si se quiere). Por tanto respondemos la opción d) Máquina de Turing.

[nosferacento]

Con lo visto hasta ahora 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 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 jun12_2a_sem_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...

[nosferacento]

PREGUNTA:  Dada la siguiente gramática regular no determinista, donde A es su símbolo inicial:

A -- > xA
A -- > yA
A -- > xB
B -- > xA
B -- > yA
B -- > xB
B -- > xC
C -- > yD
C -- > xB
D -- > λ
D -- > xB
D -- > yA

Podemos construir un autómata finito determinista con solo 2 estados que reconozca el mismo lenguaje.

a) Verdadero.
b) Falso.



RESPUESTA:

Tenemos que prestar atención al enunciado:

a)   Nos dice que es una gramática regular no determinista con símbolo inicial A
b)   Nos pregunta si podemos construir un autómata finito determinista que reconozca el mismo lenguaje

Por tanto no nos pide ni siquiera transformar la gramática en un autómata, sino ver si podemos construir un autómata que reconozca el mismo lenguaje.

Lo primero que haremos será reflexionar sobre el lenguaje y las cadenas que genera el lenguaje.

Si transformamos la gramática en autómata finito no determinista obtenemos esto:

Este autómata finito es indeterminista, pero sabemos que un AFN se puede transformar en un AFD. Ahora trataremos de encontrar algunas de las cadenas aceptadas por el autómata:

xxy: es la cadena más corta que acepta, podríamos representarla con un AFD de dos estados, uno inicial que acepta indefinidamente x y otro final al que se llega con una y. Sin embargo, aparte de ser la cadena más corta que acepta es la secuencia final obligatoria para llegar a aceptación y se permiten expresiones del tipo x(intercarlar x´s e y´s)xxy. Si usamos un estado inicial que acepta indefinidamente x´s e y´s que nos lleve a aceptación con una y, no podemos asegurar que el final será xxy. Para asegurar este final, con un AFD necesitaremos más de dos estados.

Respondemos entonces b) Falso.

Otro razonamiento: cuando se pasa de AFD a AFN se definen nuevos estados a partir del conjunto potencia de los estados del AFN. En el paso de AFD a AFN nos podemos encontrar:

a)   Caso peor: se generan 2ⁿ estados en el AFD
b)   Caso mejor: se mantienen los n estados del AFN

Por tanto el AFD no tendrá menos de 4 estados y respondemos la opción b) Falso.

Aunque con lo dicho ya no es necesario, vamos a construir el AFD usando la técnica de subconjuntos a modo de ejercicio. Para ello partimos del estado inicial y vamos representando los conjuntos de estados alcanzables (y las transiciones desde cada uno de ellos) mediante cierres ε. En este caso como no tenemos transiciones ε simplemente tenemos que fijarnos en los estados alcanzables directamente en base al símbolo leído.

	Estado	x	y	Observaciones
	{A}	{A, B}	{A}	Estado inicial
	{A, B}	{A, B, C}	{A}
	{A, B, C}	{A, B, C}	{A,D}
	{A, D}	{A, B}	{A}	De aceptación

Nos queda este autómata:

En este caso estamos en el caso “mejor”: no se ha incrementeado el número de estados respecto del AFN.

[nosferacento]

PREGUNTA: El lema del bombeo aplicado a los autómatas a pila demuestra que el lenguaje L = {xⁿyⁿzⁿ : n > 0} no puede ser reconocido por ninguna máquina.

a) Verdadero.
b) Falso.




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

Falso. Este lenguaje puede ser reconocido por una máquina de Turing. El lema de bombeo aplicado a los autómatas a pila demuestra que un lenguaje no es un LIC, y por tanto no puede ser reconocido por un autómata a pila, pero no demuestra que un lenguaje no pueda ser reconocido por ninguna máquina.

[nosferacento]

PREGUNTA: Dado el lenguaje L₁ reconocido por el autómata

y el lenguaje L₂ definido por la gramática

S -- > xSy
S -- > λ

Podemos afirmar:

a) L₁ = L₂

b) L₁ ≠ L₂   

c) L₁ ⊂ L₂

d) L₂ ⊂ L₁




RESPUESTA: la opción correcta es la b)

Hay que tener en cuenta que la gramática, lenguaje L2, obliga a que por cada x se añada una y, es decir, obliga a que el número de x y el número de y sean iguales. En cambio el lenguaje L1 permite que venga cualquier número de x y cualquier número de ys sin necesidad de que sean iguales. El lenguaje L1 está representado por un autómata finito determinista, por tanto es un lenguaje regular.

El lenguaje L2 será L2 = {xⁿyⁿ | n >= 0}. Este lenguaje requiere contar el número de x para verificar que el número de y´s sean iguales. Los autómatas finitos no tienen capacidad para contar. Por tanto este lenguaje necesita de un autómata a pila para apilar con las x y desapilar con las y´s y se trata de un LIC.

Vemos que el lenguaje L2 se diferencia además de L1 en que L1 no acepta la cadena vacía y L2 sí acepta la cadena vacía.

Por tanto la opción a) es falsa: no son lenguajes iguales.

La opción b) significa que los lenguajes son distintos, lo cual es cierto pero vamos a repasar las otras opciones.

La opción c) significaría que todas las cadenas de L1 pertenecen a L2. ¿Es cierto? No, porque en L1 estaría por ejemplo xxxy que no está en L2 por no coincidir el número de x con el número de ys.

La opción d) significaría que todas las cadenas de L2 estarían en L1, lo cual no es cierto porque la cadena vacía no está en L1.

Respondemos la opción b), son lenguajes distintos. No es difícil de ver pero requiere razonar meticulosamente y sin perder de vista detalles como la aceptación o no de la cadena vacía.

[nosferacento]

PREGUNTA: ¿Existe algún lenguaje independiente del contexto no regular compuesto por un número finito de palabras?

a) Sí.
b) No.



RESPUESTA: la opción correcta es la b)

Si el lenguaje estuviera compuesto por un número finito de palabras sería representable por un autómata finito y por tanto sería un lenguaje regular. Para ser un LIC no regular debe admitir infinitas palabras, por tanto respondemos la opción b).

Adicionalmente indicaremos que: todo lenguaje con un número finito de palabras es regular. Es cierto que con muchas palabras quizás nos salieran autómatas finitos gigantescos, pero seguiría siendo un lenguaje regular.

[nosferacento]

PREGUNTA: Sea L₂ = {xⁿyⁿzⁿ | n > 0}. Y sea L₁ el lenguaje reconocido por la siguiente máquina de Turing.

¿Cuál de las siguientes afirmaciones es correcta?


a) L1 = L2

b) L1 ≠ L2   

c) L1 ⊂ L2

d) L2 ⊂ L1




RESPUESTA: hay dos opciones que podrían considerarse correctas, la b y la d. Nosotros nos decantamos por responder la d) (ver el razonamiento seguido a continuación)

Nota: fijarse que el símbolo B o blanco de la máquina de Turing aquí lo representan con un espacio vacío. Es decir, la transición de q1 a q2 es B;B, -->, etc. En otras ocasiones también se representa con un cuadradito vacío.

Tratemos de ver qué es lo que hace la máquina de Turing propuesta. Vemos que en la transición de q0 a q1 requiere una x, en la transición de q2 a q3 requiere una y, y en la transición de q4 a q5 requiere una z.

Nos preguntamos ¿admite la MT la cadena zyx? Para esta cadena tenemos estas transiciones: q0zyx ├ zq0yz ├ zyq0x ├ zq1yx ├ q1zyx ├ q1Bzyx ├ q2zyx ├ zq2yx ├ q3zyx ├ q3Bzyx ├ q4zyx ├ q5Bzyx

Efectivamente la máquina admite esta cadena. La máquina parece admitir cualquier cadena que contenga al menos una x, una y y una z sin requerir un orden específico.

Si tratamos de ver lo que hace, en primer lugar se mueve a derechas hasta encontrar una x. Luego vuelve al principio de la cadena, hasta encontrar el blanco inicial. Luego se mueve a derechas hasta encontrar una y, y seguidamente vuelve al principio de la cadena, hasta encontrar el blanco inicial. Luego se mueve a derechas hasta encontrar una z y acepta.

Hemos visto que admite zyx y esta cadena no pertenece al lenguaje L2, por tanto descartamos tanto la opción de que L1 = L2 como la opción de que L1 sea un subconjunto de L2.

La opción b podemos decir que es verdadera, pero nos preguntamos si la opción d es también verdadera.

L1 reconoce cualquier cadena que contenga al menos una x, una y una z, por tanto reconoce todas las cadenas en el lenguaje L2 que han de tener obligatoriamente una x, una y y una z. Por tanto es cierto que L2 es subconjunto de L1.

Respondemos la opción d) porque es la que mejor describe la situación, aunque dado que la opción b) puede considerarse cierta y por tanto generar dudas, recomendamos escribir un comentario al respecto en el examen, en una hoja aparte.

[nosferacento]

PREGUNTA: La siguiente gramática con símbolo inicial S:

S -- > AB
A -- > Aa
A -- > a
B -- > Bb
B -- > b

a) Es una gramática regular.
b) Es una gramática independiente del contexto.
c) Ninguna de las anteriores.




RESPUESTA: la opción correcta es la b) (esta pregunta tiene “truco”, ver la explicación).

Trataremos de analizar qué cadenas genera la gramática. No hay derivaciones a la cadena vacía, por tanto la cadena vacía no forma parte del lenguaje. A puede derivar a una cadena con un mínimo de una a y un máximo de infinitas a´s. B puede derivar a una cadena con un mínimo de una b y un máximo de infinitas b´s. El símbolo inicial puede derivar a como mínimo ab, y a cualquier cadena con cualquier número de a´s antecediendo a cualquier número de b´s. Esto equivale a la expresión regular aa*bb*. ¿Siempre que una gramática representa un lenguaje regular es una gramática regular? Intuitivamente quizás respondamos que sí, pero lo cierto es que no, ahí está el truco o sutileza de esta pregunta.

Por ello nos tenemos que remitir a la definición de gramática regular. Una gramática es regular si cumple estos requisitos:

a)   En el lado izquierdo de las reglas de producción solo aparece un símbolo
b)   El lado derecho de las normas sólo puede contener dos cosas: un símbolo terminal (se acepta también la cadena vacía) ó un símbolo terminal seguido de un símbolo no terminal.

Por tanto no se aceptan reglas como A -- > Aa porque el símbolo no terminal no puede aparecer como primer símbolo en el lado derecho.

Tampoco se aceptan reglas como A -- > AB porque tiene dos símbolos no terminales seguidos en el lado derecho de la regla, por tanto la gramática propuesta no es regular.

Dado que los lenguajes regulares son un subconjunto de los lenguajes independientes del contexto y dado que las gramáticas independientes del contexto aceptan que en el lado derecho haya cualquier sucesión de símbolos (terminales o no terminales) concluimos que la gramática es una gramática independiente del contexto que genera un lenguaje regular.

Pregunta que parecía sencilla pero que ha resultado bastante más complicada de responder de lo que aparentaba.