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

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

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

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

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 – { λ }

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.

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.

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.

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!

PREGUNTA: Dado un alfabeto Σ,llamamos L1 al conjunto de lenguajes de Σ aceptados por máquinas de Turing deterministas de una sola cinta, L2 al conjunto de lenguajes de Σ aceptados por máquinas de Turing deterministas con varias cintas y L3 al conjunto de lenguajes de Σ aceptados por máquinas de Turing no deterministas y con varias cintas

¿Cuál de las siguientes afirmaciones es verdadera?

a) L1 = L2 ⊂ L3

b) L1 ⊂ L2 = L3

c) Ninguna de las anteriores afirmaciones es cierta




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

La capacidad de reconocimiento de lenguajes es la misma para máquinas de Turing deterministas de una cinta, de varias cintas o no deterministas de una o varias cintas. Lo que sí puede variar es la eficiencia o tiempo necesario para resolver un problema entre máquinas deterministas y no deterministas, pero en este caso no hablamos de la eficiencia o complejidad temporal de las máquinas, sino de la capacidad de reconocimiento de lenguajes.

La opción a) indicaría que las máquinas deterministas reconocen un conjunto de lenguajes que es subconjunto de los que reconocen las máquinas no deterministas, lo cual es falso.

La opción b) indicaría que las máquinas deterministas de una cinta reconocen menos lenguajes que las máquinas deterministas de varias cintas o que las máquinas no deterministas, lo cual es falso.

Si se quiere hacerlo más simple, recordar esto: todas las máquinas de Turing tienen la misma capacidad de reconocimiento de lenguajes.

Conclusión: respondemos la opción c), ninguna de las afirmaciones anteriores es cierta.

Te respondo a través de un nuevo tema del foro para no mezclar