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

[nosferacento]

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

[nosferacento]

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

b) Si, pero sólo podría sumar hasta nueve, ya que sólo se puede usar la cima de la pila.

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

d) Ninguna de las anteriores









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

Las posibles combinaciones de a, b, c, d, e aunque sean un número muy grande son un número finito, y se podrían representar con un autómata finito. Un autómata a pila podría contar el número de vocales poniendo un símbolo en la pila cada vez que detecte una vocal. La cuestión es: ¿podría hacerse usando únicamente la cima de la pila? Sí, ya que podemos definir transiciones para que en cada rama del autómata se vaya cambiando el símbolo de cima de pila cada vez que se lea una nueva vocal (tener en cuenta que no estaríamos limitados por 9 números, ya que podemos establecer una equivalencia entre un símbolo y un número y el número de símbolos de pila que podemos usar es tan grande como queramos).

Si las cadenas permitidas fueran de longitud infinita no podríamos, ya que el alfabeto de pila no puede ser infinito.

[nosferacento]

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.

[nosferacento]

PREGUNTA: Dada la siguiente máquina de Turing:

M = ( {qo, q1, q2, q3, q4}, {0,1}, {0, 1, X, Y, B}, σ, q0, B, {q4})

donde σ se define mediante la siguiente tabla de transiciones:

Nota: dado que no se ve del todo bien, aclarar que la anotación más a la derecha y más abajo es (q4, B, R)


Indicar cuál de las siguientes afirmaciones es verdadera:

a) El lenguaje que reconoce es {0ⁿ1ⁿ: n >= 0}

b) El lenguaje que reconoce es {0ⁿ1ⁿ: n >= 1}

c) El lenguaje que reconoce es {0^m1ⁿ:  m, n >= 0}

d) Ninguna de las anteriores afirmaciones es verdadera









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

Lo primero que hemos de preguntarnos es cuál es el estado de aceptación de la máquina. Esto nos lo indica la definición M = … donde el último término son los estados de aceptación, en este caso es estado de aceptación q4.

Nos podemos preguntar: ¿Por qué aparecen los símbolos X, Y, B en la tabla de transiciones si el alfabeto del lenguaje está formado por 0, 1? La respuesta es que en las máquinas de Turing los símbolos que generan transiciones son los símbolos de cinta, que son los que determinan las transiciones. La cadena inicial únicamente interviene para inicializar la cinta (por tanto después de algunos movimientos podemos encontrarnos que estamos leyendo cualquier símbolo de cinta, no sólo símbolos del alfabeto del lenguaje).

Nos preguntamos: ¿admite la máquina la cadena vacía? No, para salir de q0 necesitamos que la cadena a reconocer empiece por cero. Por tanto la opción c donde n >= 0 con n=0 sería falsa (no admite la cadena vacía). Descartamos la opción c).

Por el mismo motivo la opción a) {0ⁿ1ⁿ: n >= 0} es falsa (al no admitirse la cadena vacía). Descartamos la opción a).

Nos preguntamos si la opción b) es cierta.

 ¿admite la máquina la cadena 01? Las transiciones serían:

q₀01 ├ Xq₁1 ├  q₂XY ├  Xq₀Y ├ XYq₃B├ XYBq₄ B … con lo que llegamos a aceptación, lo que apunta a que la opción b) puede ser correcta.

¿admite la máquina la cadena 0101? Las transiciones serían:

q₀0101 ├ Xq₁101 ├  q₂XY01 ├  Xq₀Y01 ├ XYq₃01 ├ … en q₃ no hay transición definida para un cero, por lo tanto la máquina se para y la cadena no es admitida, esto apunta a que la opción b) puede ser correcta.

¿admite la máquina la cadena 0011? Las transiciones serían:

q₀0011 ├ Xq₁011 ├ X0 q₁11 ├ Xq₂0 Y1 ├ q₂X0 Y1 ├ X q₀0Y1 ├ XX q₁Y1 ├ XX q₁Y1 ├        XX Y q₁1 ├ XXq₂YY ├ X q₂XYY ├ XXq₀YY ├ XXY q₃Y ├ XXYY q₃B ├ XXYYBq₄ B … con lo que llegamos a aceptación, lo que apunta a que la opción b) puede ser correcta.

Respondemos por tanto la opción b).

Quizás sea más fácil en algunos casos verlo haciendo la representación de la máquina de Turing de forma gráfica, que hubiera sido otra forma de enfocar el problema o de tratar de verificarlo. Esta representación sería la siguiente:

[nosferacento]

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.

[nosferacento]

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

a) El número total de lenguajes no regulares es finito

b) El número total de lenguajes regulares es finito

c) Ninguna de las afirmaciones anteriores es cierta











RESPUESTA: la opción correcta es la c

La a) es falsa porque el número total de lenguajes no regulares es infinito, podemos definir tantos lenguajes como queramos.

La b) es falsa por el mismo motivo.

Respondemos por tanto la opción c).

[nosferacento]

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

[nosferacento]

PREGUNTA: El lenguaje L =  {0ⁱ1^j2^k  | i < j < k}


a) Es independiente del contexto determinista

b) Es independiente del contexto no determinista

c) Es recursivamente enumerable y no independiente del contexto









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

Para reconocer el lenguaje necesitamos contar el número de ceros, el número de unos y el número de 2´s. Para ser independiente del contexto tendríamos que poder reconocerlo con un autómata a pila.

RAZONAMIENTO ERRÓNEO: Podríamos hacer lo siguiente con un autómata a pila: apilar ceros en un estado q0 y definir una transición para paso a un estado q1 donde al recibir 1´s desapilamos los ceros. Si el número de 1´s fuera igual o superior al de ceros, tendríamos una transición a un estado “error”. Otra transición nos llevaría a q2 si recibimos un 2, donde desapilaríamos los unos. Si el número de 2´s fuera igual o superior al de unos tendríamos una transición a un estado “error”. Una transición espontánea leyendo la cadena vacía nos llevaría a un estado q3 donde desapilaríamos todo sin leer caracteres hasta vaciar la pila y pasar a aceptación en q4.
El autómata sería no determinista, ya que tiene una transición usando la cadena vacía que puede ser una transición aplicable al mismo tiempo que otra transición ante un carácter de entrada. Sin embargo, como es condición de aceptación leer la cadena de entrada al completo, sólo llegaríamos a aceptación si se consume la cadena de entrada y se cumplen las condiciones previstas.

¿POR QUÉ ES ERRÓNEO ESTE RAZONAMIENTO? Porque hemos dicho “Otra transición nos llevaría a q2 si recibimos un 2, donde desapilaríamos los unos”. Pero los unos no pueden apilarse, ya que están siendo utilizados para desapilar los ceros.

Para poder reconocer el lenguaje necesitaríamos mantener información sobre el número de 1´s para compararlo con el número de 0´s y sobre el número de 1´s para compararlo con el número de 2´s. Con una pila sólo podríamos hacer una comparación, para poder hacer dos necesitaríamos dos pilas y ya no sería un lenguaje independiente del contexto.

Respondemos por tanto la opción c), es recursivamente enumerable no independiente del contexto.

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

[nosferacento]

PREGUNTA: Sea el alfabeto Σ = {a, b}. Sea L1 el lenguaje reconocido por el autómata con cinco estados y L2 el lenguaje reconocido por el autómata con tres estados.

Indicar cuál de las siguientes afirmaciones es verdadera:

a) Uno de los autómatas es determinista y el otro no lo es

b) El autómata de la izquierda tiene algún estado no accesible

c) L1 = L2

d) Ninguna de las anteriores afirmaciones es verdadera











RESPUESTA:

Analizamos el autómata con 5 estados: es determinista. Analizamos el autómata con 3 estados: es determinista. Luego la opción a) es falsa.

En el autómata con 5 estados todos sus estados son accesibles. Por tanto la opción b es falsa.

Para la opción c nos preguntamos ¿son ambos lenguajes iguales? El autómata de la izquierda reconoce la cadena vacía y el de la derecha también.

En el autómata de la izquierda el estado E es irrelevante por lo que podemos ignorarlo. Si vamos escribiendo las posibles opciones de expresiones alternativas que permiten llegar a aceptación y vamos eliminando duplicados, llegamos a la conclusión de que el lenguaje reconocido es (a* (ba)* | b)

En el autómata de la derecha el estado C es irrelevante por lo que podemos ignorarlo. Podemos ver que el lenguaje reconocido es el lenguaje (a* (ba)* | b) mismo que el del otro autómata, por tanto L1 es igual a L2 y respondemos la opción c).

[nosferacento]

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.

[nosferacento]

PREGUNTA: Las máquinas de Turing se diferencian de los autómatas finitos y de los autómatas a pila en que:

a) En las máquinas de Turing la cabeza lectora puede retroceder

b) Las máquinas de Turing pueden escribir sobre su cinta

c) Las dos afirmaciones anteriores son ciertas








RESPUESTA: la opción correcta es la c). Los autómatas a pila y los autómatas finitos no tienen cabeza lectora que pueda retroceder ni tienen cinta.

La opción a es cierta y la opción b es cierta, por tanto respondemos la opción c).

[nosferacento]

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

a) L = {w ∈ {a, b}* | ab y ba son subcadenas de w}

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

c) El lenguaje de cadenas que son prefijos (finitos) de la expansión decimal del número pi (π), es decir, L = {3.1 ,3.14, 3.141 ,3.1415, ... }







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

La definición de los lenguajes es un poco “extraña” y se puede interpretar así. Para la opción a, se trata del lenguaje (ab)* con la condición de que ab y ba estén presentes dentro de las cadenas del lenguaje (sin importarnos en qué posición).

Opción a): Esto se puede expresar como expresión regular tipo ya que el número de posiciones posibles de ab y ba es un número finito. Podemos tener ab – otro – ba, ab – ba – otro, ba – otro – ab, ba – ab – otro, otro – ab – ba, otro – ba – ab … y estas combinaciones se pueden expresar como (ab (ab)* ba | abba (ab)* | ba (ab)* ab | … etc.

Otra forma de razonarlo: ¿podemos dibujar un autómata finito que reconozca el lenguaje? Sí, basta un autómata que tenga dos ramas: una de ellas que contemple la posibilidad de recibir ab primero y ba después, y la otra que contemple la posibilidad de recibir ba primero y ab después.

Opción b: lo podemos representar con un autómata finito cuyo lenguaje es a, b y cuyo estado inicial es aceptación, con toda a vuelve al estado inicial, mientras que con tres b´s va a un estado muerto (del que no puede salir).

Opción c: la expansión decimal de pi genera infinitos prefijos finitos, y esto no lo podemos representar con un autómata finito. Por tanto, respondemos la opción c).

Otra forma de razonarlo es que un lenguaje infinito para ser regular ha de cumplir el lema de bombeo. En este caso no lo cumple: no podemos subdividir y bombear parte de la cadena y seguir perteneciendo la cadena al lenguaje, luego no es regular

[nosferacento]

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

S -- >  xxSyy | ε

y el siguiente autómata (Nota: Se supone que la pila se encuentra inicialmente vacía):

¿Qué significado se le puede atribuir al estado par cuando el autómata lee cadenas del lenguaje L?

a) Se llega al estado par cuando se ha leído un número par de x's en las cadenas del lenguaje L.

b) Se llega al estado par cuando se ha leído un número par de símbolos en las cadenas del lenguaje L.

c) Se llega al estado par cuando se ha leído un número par de y's en las cadenas del lenguaje L.

d) Se llega al estado par cuando se ha leído un número impar de x's en las cadenas del lenguaje L.











RESPUESTA:

Las cadenas del lenguaje L son cadenas con un número de caracteres par y formadas por el mismo número de x´s que de y´s.

Si analizamos lo que hace el autómata a pila, cuando lee una x pasa al estado par y escribe una a como cima de pila. Con la siguiente x vuelve al estado S, con la siguiente x vuelve al estado par… y así sucesivamente hasta que empiece a leer las y´s. Por tanto se llega al estado par cuando se ha leído un número impar de x's en las cadenas del lenguaje L. Es decir, la opción correcta es la d).

La pregunta es sencilla siempre que no nos liemos con el nombre del estado. Que el estado se llame par no tiene necesariamente que tener un significado, también se podría haber llamado “manzana”.

[nosferacento]

PREGUNTA: Indicar para qué valores de las etiquetas Etiqueta-1 y Etiqueta-2, el autómata de la figura representa el lenguaje {xⁿ⁺¹ yⁿ : n >=0}. Se supone que inicialmente la pila se encuentra vacía y que el símbolo inicial de la pila es Zo.

a) Etiqueta-1= x, ε; z  Etiqueta-2= ε, z; ε

b) Etiqueta-1 = x, ε; y  Etiqueta-2 = ε, ε; ε

c) No existen valores de Etiqueta-1 y Etiqueta-2 que hagan correcta la solución











RESPUESTA:

Si nos fijamos en q2, por cada y leída se quita una z de la pila. Si necesitamos que el número de x´s sea uno más que el de y´s, nos interesa un autómata no determinista que consuma x´s en q1 añadiendo z´s a la pila, pero que lea una x sin añadir z a la pila para hacer la transición a q2. De esta manera, en la pila nos quedan un número de z´s que es igual al de x menos una. En q2 se desapila una z con cada carácter y leído y al vaciar la pila se pasa a aceptación en q3. Por tanto Etiqueta-1 debe añadir z´s a la pila, y debería ser x, ε; z para reconocer la primera x, junto a x, z; zz para reconocer las x´s adicionales.

Etiqueta 2 debería ser x, z; z para reconocer la última x.

Con la opción a) etiqueta 1 consume x´s dejando una z en la cima de pila y etiqueta 2 lleva a q2 de forma espontánea eliminando la z en la cima de pila, pero esto no asegura que el número de x´s leído sea uno más que el número de y´s.

Con la opción b) se consumen x´s dejando una y en cima de pila y se pasa a q2 donde no habría transición posible al no existir una z en cima de pila.

Por tanto respondemos la opción c), ninguna de las alternativas planteada es válida.

[nosferacento]

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

S -- > xxSyy | xxyy

y el siguiente autómata (Nota: Se supone que la pila se encuentra inicialmente vacía):

Indicar cuál de las siguientes afirmaciones es verdadera:

a) El autómata no comprueba que haya un número par de y's en las cadenas del lenguaje L.

b) El autómata no reconoce todas las cadenas contenidas en el lenguaje L.

c) El autómata reconoce todas las cadenas contenidas en el lenguaje L.

d) El autómata no está correctamente definido.










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

Las cadenas del lenguaje L son cadenas con un número de caracteres par y formadas por el mismo número de x´s que de y´s. El lenguaje no admite la cadena vacía, siendo la cadena más corta admitida xxyy.

El autómata desde S pone z en cima de pila y pasa al estado X, donde permite leer un número par de x´s poniendo una a en cima de pila por cada x leída. Cuando se lee una y se desapila una a y se pasa al estado Y. Ahí se elimina una a de la pila por cada carácter y recibido. Si la pila está vacía se pasa al estado de aceptación F.

Opción a): es falsa. Si el autómata no verifica que hay un número par de y´s, además siendo el número de x´s igual al de y´s, entonces no pasa a aceptación.

Opción b): es falsa. El autómata sí reconoce todas las cadenas del lenguaje.

Opción c) es verdadera.

Opción d) es falsa.

[nosferacento]

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 afirmaciones anteriores es cierta









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

Todas las máquinas de Turing, independientemente del número de cintas de que consten o de que sean deterministas o no, tienen la misma capacidad de reconocimiento de lenguajes y los lenguajes que reconocen se denominan Lenguajes Recursivamente Enumerables (LRE). El número de cintas puede variar la eficiencia u orden de complejidad con que una máquina te Turing resuelve un cómputo, pero no modifica los lenguajes reconocibles. Por tanto L1 = L2 = L3

Y ninguna de las afirmaciones anteriores es cierta. La opción correcta es la c).

[nosferacento]

PREGUNTA: Dada la siguiente gramática G:

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

y la expresión regular E = 0*1 (0 + 1) * . Indicar cuál de las siguientes afirmaciones es verdadera:

a) G y E no pueden generar el mismo lenguaje porque la gramática es independiente del contexto (y por tanto, generará un lenguaje independiente del contexto) y la expresión regular generará un lenguaje regular

b) Ambos reconocen el mismo lenguaje

c) Ninguna de las anteriores afirmaciones es verdadera








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

Si analizamos el lenguaje generado por la gramática tenemos que la palabra más corta aceptada es 1, y que se pueden generar cadenas con tantos ceros iniciales como se desee y con tantos ceros o unos finales intercalados como se desee. Esto lo podemos representar con una expresión regular: 0* 1 (0+1)*, por tanto la gramática y la expresión regular generan el mismo lenguaje y la opción cierta es la b).

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.

Recordar que todos los lenguajes regulares son a su vez lenguajes independientes del contexto.

[nosferacento]

PREGUNTA: El resultado de concatenar dos lenguajes independientes de contexto, ¿es siempre un lenguaje independiente de contexto?

a) Sí, siempre

b) No, nunca

c) Depende de los lenguajes que se consideren









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 o 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, 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]

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