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

[nosferacento]

Dado el lenguaje L = {xⁿyⁿzⁿ : n > 0} que es reconocible con un autómata a pila con dos pilas. ¿Es posible construir una máquina de Turing que simule el uso de esas dos pilas?

a) Verdadero.

b) Falso.





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

La máquina de Turing es la máquina con mayor capacidad de reconocimiento de entre las que se toman en consideración en teoría de autómatas, por tanto todo autómata que reconozca un lenguaje puede ser emulado por una máquina de Turing.

[nosferacento]

PREGUNTA: La máquina de Turing representada a continuación, no controla el orden de aparición de los elementos del alfabeto Σ = {x, y}

a) Verdadero.
b) Falso.




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

Se nos plantea un “pequeño problema” que consiste en que habitualmente el símbolo λ no se usa en las máquinas de Turing mientras que aquí sí aparece. ¿Lo consideramos como que representa el “blanco” de la máquina de Turing o como un símbolo distinto? Esto debería aclararlo el enunciado pero no lo hace.

En principio optaríamos por considerar que representa el blanco, ya que escribir en una casilla la cadena vacía sería dejar la casilla en blanco (esto normalmente se representa con una B, pero en este caso consideraremos que λ equivale al símbolo B).

Supongamos ahora que λ representa lo mismo que B.

La máquina acepta la cadena vacía (si lee blanco, pone S en la cinta y acepta). En relación a cadenas, yx no es aceptada ya que para comenzar a trabajar la máquina ha de recibir una x. Supongamos que recibe xy:

q0xy ├ aq1y├ ayq1B ├ aq2y ├ q3a ├ q0Bx ├ FSx y acepta

Dado que la máquina acepta xy pero no acepta yx podemos decir que sí controla el orden en que aparecen los elementos del alfabeto. A la pregunta ¿ no controla el orden de aparición de los elementos del alfabeto Σ = {x, y}?

La respuesta es falso, opción b), ya que sí controla el orden de aparición.

Pregunta un tanto difícil de interpretar, sobre todo saber qué es lo que están preguntando  .

[nosferacento]

PREGUNTA: Dado el siguiente autómata

podemos afirmar:
 
a) Reconoce el lenguaje L definido por la expresión regular x*y*

b) Reconoce el lenguaje L = {xⁿyⁿ : n > 0}

c) Reconoce el lenguaje L = {xⁿy²ⁿ : n > 0}

d) Reconoce un lenguaje que se puede expresar como la unión de dos lenguajes independientes del contexto.





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

Se trata de un autómata a pila que reconoce la gramática:

S -- > A
S -- > B
A -- > xAy
B -- > xxBy
A -- > xy
B --  > xxy

La gramática forma dos ramas de lenguaje, la que deriva de la A y la que deriva de la B.

A partir de la A tenemos cadenas que empiezan por x y tienen un número de x igual al número de y´s, por tanto admite xy, xxyy, xxxyyy, etc., sublenguaje xⁿyⁿ

A partir de la B tenemos cadenas que empiezan por x y tienen el doble de x que de y´s, por tanto admite xxy, xxxxyy, xxxxxxyyy, sublenguaje x²ⁿyⁿ

El lenguaje admitido por el autómata podríamos definirlo como L = { xⁿyⁿ U x²ⁿyⁿ tal que n >0 } donde U representa unión.

¿Reconoce el lenguaje x*y*? No, porque x*y* admite la cadena vacía y este lenguaje no la admite.

 ¿Reconoce el lenguaje L = {xⁿyⁿ : n > 0} ? Sí, este es un lenguaje independiente del contexto. Pero además reconoce más cadenas que las definidas por este lenguaje.

¿ Reconoce el lenguaje L = {xⁿy²ⁿ : n > 0} ? Sí, este es un lenguaje independiente del contexto. Pero además reconoce más cadenas que las definidas por este lenguaje.

¿Reconoce un lenguaje que se puede expresar como la unión de dos lenguajes independientes del contexto.? Sí, esta es la respuesta más acertada (aunque las respuestas b) y c) también serían verdaderas, pero incompletas o “no del todo exactas”).

Respondemos por tanto la opción d).

[nosferacento]

PREGUNTA: ¿Cuál de los siguientes autómatas tienen mayor capacidad de representación?:

a) Los autómatas a pila no deterministas.

b) Los autómatas a pila deterministas.

c) Todos los autómatas anteriores tienen la misma capacidad de representación.





RESPUESTA:

Los autómatas a pila no deterministas tienen una mayor capacidad de representación que los autómatas a pila deterministas. Si hiciéramos un diagrama representando como conjuntos los lenguajes, tendríamos que los lenguajes regulares quedan englobados dentro de los lenguajes aceptados por autómatas a pila deterministas, y estos a su vez quedan englobados por los lenguajes aceptados por autómatas a pila no deterministas, y estos a su vez quedan englobados por los lenguajes aceptados por máquinas de Turing.

[nosferacento]

PREGUNTA: El lema del bombeo aplicado a las máquinas de Turing implica:

a) Nada, ya que sólo se aplica a los lenguajes generados por gramáticas independientes del contexto

b) La existencia de problemas no resolubles por autómatas a pila.

c) La existencia de problemas no resolubles por máquinas de Turing, como por ejemplo, el problema de parada.







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

Existe un lema de bombeo para lenguajes regulares (sirve para demostrar que un lenguaje no es regular) y un lema de bombeo para lenguajes independientes del contexto (sirve para demostrar que un lenguaje no es independiente del contexto). No hay aplicación de lema de bombeo a las máquinas de turing.

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {a, e, i, O, u}. Definimos el concepto sílaba como cualquier ordenación de los cinco elementos del alfabeto sin repetición. Si definimos un lenguaje cuyas palabras se forman como la concatenación de un número impar de sílabas, podemos afirmar que:

a) El lenguaje es regular.

b) El lenguaje es independiente del contexto finito no regular.

c) El lenguaje es independiente del contexto infinito no regular.

d) El lenguaje es recursivamente enumerable no independiente del contexto.








RESPUESTA:

Un número impar es infinito, por tanto descartamos la opción b.

Ahora nos preguntamos ¿la máquina más simple que puede reconocer este lenguaje será un autómata finito (en cuyo caso será lenguaje regular), un autómata a pila (en cuyo caso será independiente del contexto infinito no regular) o una máquina de Turing (en cuyo caso será recursivamente enumerable, reconocible por máquinas de Turing).

¿Qué son sílabas? Son sílabas aeiou, aeiuo, aeoiu, aeoui… hasta concluir con un número finito de sílabas (puede ser grande, pero es finito). Si es finito, toda sílaba se puede representar con un autómata finito no determinista que tuviera muchas ramas, cada una de las cuales representa una sílaba (por ejemplo una rama sería a-e-i-o-u, otra rama sería a-e-i-u-o, y así sucesivamente).

El carácter impar de una concatenación de sílabas lo podemos representar con un autómata finito no determinista que reconoce tres sílabas determinadas una después de otra y con un nuevo carácter vuelve a la segunda sílaba (a su primer carácter, de modo que ahí le faltarían dos sílabas para llegar a aceptación).

Posiblemente salga un autómata de cientos o miles de estados, pero se podría representar usando un autómata finito no determinista por lo que respondemos la opción a), el lenguaje es regular.

Esta pregunta no es nada sencilla de responder… así que no te sientas mal si no has sido capaz de responderla 

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

[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) Sí, pero se tiene que enseñar al autómata a sumar.

b) Sí, utilizando notación no decimal.

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

d) Sí, si se cumplen todas las condiciones anteriores.







RESPUESTA: la opción correcta es la d), pero ver comentarios.

Esta pregunta es un tanto confusa. El enunciado no es claro, con lo cual no podemos dar un razonamiento lógico como en otras preguntas. Nos limitamos a indicar que la respuesta “oficial” es que “todo lo que hace un autómata a pila es enseñado, por lo que a) es cierta. La notación decimal sólo permitiría contar hasta 9, por lo que hemos de usar notación no decimal y b) es cierta. c) es cierta porque si no no se podrían reconocer cadenas. Y d) es por tanto cierta.

No comments…

[nosferacento]

PREGUNTA: Dada la gramática:

S -- > xSy | ySx | ySy | xSx | ε

Indicar cuál es lenguaje que genera:

a) El lenguaje formado por cualquier cadena de x's e y's.

b) El lenguaje formado por cualquier cadena de x's e y's, incluida la palabra vacía.

c) El lenguaje formado por cadenas que tengan el mismo número de x's que de y's .

d) El lenguaje formado por cualquier cadena de x's e y's de cardinalidad par, incluida la palabra vacía.








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

El símbolo inicial S puede derivar a la cadena vacía ε, por tanto la cadena vacía está incluida dentro del lenguaje.

Veamos cadenas que admite el lenguaje:

Por la primera producción: xy, xxyy, xxxyyy … son cadenas con el mismo número de x´s que de y´s

Por la segunda producción: yx, yyxx, yyyxxx … son cadenas con el mismo número de x´s que de y´s

Por la tercera y cuarta producción tenemos cadenas con un número par de x´s o de y´s

Dado que la S se puede introducir en cualquiera de las producciones, también se generan cualquier mezcla de las cadenas anteriores como xSy, xyxy; yySxx, yyxxxyyyyy

La opción a) la descartamos, porque si fuera cierta la opción b) sería más cierta ya que la cadena vacía forma parte del lenguaje.

La opción c) es falsa porque la cadena yy se admite en el lenguaje y no tiene el mismo número de x´s que de y´s.

La diferencia entre la opción d) y la b) es que la d) nos indica que las cadenas han de ser de cardinalidad par (incluida la cadena vacía, que puede verse como una cadena de cardinalidad cero). ¿Es esto cierto? Sí, porque toda regla introduce dos símbolos, por tanto toda cadena será de cardinalidad par.

Por tanto respondemos la opción d).

[nosferacento]

PREGUNTA: Dados dos lenguajes independientes del contexto L1 y L2 , indicar cuál de las siguientes afirmaciones es verdadera:

a) L1 ∩ L2  siempre es independiente del contexto

b) L1 + L2  siempre es independiente del contexto

c) L1 - L2  siempre es independiente del contexto








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

Tenemos que remitirnos a las propiedades de los lenguajes independientes del contexto.

La intersección de dos lenguajes independientes del contexto no siempre es un lenguaje independiente del contexto, por tanto la opción a) es falsa. Nota: sin embargo, la intersección de dos lenguajes regulares sí es regular.

La opción b) o suma de los dos lenguajes, es equivalente a la unión de los dos lenguajes. La unión de dos LIC siempre es un LIC, por tanto la opción b) es verdadera

La opción c) o lenguaje 1 excepto las cadenas del lenguaje 2 no necesariamente es un LIC. Dados dos lenguajes LIC, su diferencia no necesariamente es un LIC.

Ya que estamos, recordar lo siguiente: los LIC son cerrados para: la unión, la concatenación, la clausura o estrella de kleene, la clausura positiva y el homomorfismo. No son cerrados para la intersección, la complementación ni la diferencia.

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {0, 1}, se define L como el lenguaje formado por las cadenas que cumplen que N(0) = N(1) + 1 donde N(0) es el número de apariciones del símbolo 0 y N(1) es el número de apariciones del símbolo 1. Indicar cuál de las siguientes gramáticas independientes del contexto genera L.

a)   S -- > CB | BC | 0C1 | 1C0 | 0
       C -- > 0C1 | 1C0 | 0
       B -- > 0B1 | 1B0 | 01 | 10


b)   S -- > 0A1 | 0
       A -- > 0A1 | 0B | 0
       B -- > 0B | 0


c)   S -- > CB | BC | 0C1 | 1C0 | 0 | ε
       C -- > 0C1 | 1C0 | 0
       B -- > 0B1 | 1B0 | 01 | 10










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

El lenguaje comprende las cadenas donde el número de ceros es igual al número de unos más uno, por ejemplo: 100 (aparece cero una vez más que el 1), 11000, 1110000.
Como no indica nada relativo al orden se admite también 010, 001, 00011, 01010, etc.
¿Se admite 0? Sí, caso de que el número de unos es cero y el número de ceros es una unidad más que el número de unos. ¿Se admite 1? No, en este caso el número de ceros tiene que ser dos. ¿Se admite 01? No ¿Se admite 10? No ¿Se admite la cadena vacía? No, porque no cumple que el número de ceros sea uno más que el número de unos.

La opción b) no permite derivar cadenas que empiecen por 1, por tanto no representa el lenguaje.

La opción c) se descarta por admitir la cadena vacía.

 La opción a) permite derivar el cero, cadenas que empiecen por 0 o por 1 y que permiten añadir pares de ceros y unos en cualquier orden para cerrarse han de derivar la C a cero, lo cual supondrá que la cadena tenga un número de ceros una unidad superior al número de unos.  Respondemos por tanto la opción a).

[nosferacento]

PREGUNTA:  Considere el siguiente autómata a pila.

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

a) El autómata es determinista y acepta el lenguaje {xⁿ⁺² yⁿ   | n >= 0}

b) El autómata es no determinista y acepta el lenguaje {xⁿ⁺² yⁿ   | n >= 0}

c) El autómata no siempre llega al estado de aceptación con la pila vacía

d) Ninguna de las anteriores afirmaciones es verdadera








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

En el estado B tenemos dos transiciones para un mismo símbolo de entrada (x), por tanto el autómata no es determinista y descartamos la opción a).

¿Acepta el lenguaje de cadenas que empiezan por x´s y tienen dos x´s más que y´s, incluido n=0 que supone que se admita xx? Podemos admitir una x sin tomar en consideración la cima de pila (cadena vacía) y poner una z. A continuación leemos una x y teniendo z en cima de pila la eliminamos poniendo la cadena vacía, con lo que nos queda Zo. Seguidamente con Zo pasamos de C a D y aceptamos.

¿Se acepta xxxxyy? Leemos tres x´s y ponemos tres z´s en la pila, luego leemos una x y eliminamos una z de la pila, luego leemos dos y´s y eliminamos las dos z´s que quedaban en la pila, y aceptamos pasando a D.

Siempre podremos aceptar este tipo de cadenas, luego la opción b) resulta cierta.

Para llegar a aceptación siempre hemos de hacerlo con la pila conteniendo el símbolo de fondo de pila (pila vacía), luego la opción c) es falsa.

Respondemos por tanto la opción b).

[nosferacento]

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

[nosferacento]

PREGUNTA: A la hora de trasladar la cabeza de la máquina de Turing en cada paso de ejecución de la máquina. ¿Cuál de las siguientes afirmaciones es verdadera?

a) Las máquinas de Turing sólo pueden moverse una posición a la derecha.

b) Las máquinas de Turing sólo pueden moverse una posición a la izquierda.

c) Las máquinas de Turing sólo pueden moverse una posición a la derecha o a la izquierda.

d) Las máquinas de Turing pueden moverse cualquier número de posiciones a la derecha o a la izquierda.










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

En una máquina de Turing clásica en cada paso de computación de la máquina la cabeza se mueve una posición a la izquierda o a la derecha.

[nosferacento]

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.

[nosferacento]

PREGUNTA: Sea L el lenguaje sobre el alfabeto Σ = {0, 1} cuyas cadenas verifican las siguientes restricciones: "si una cadena tiene menos de cinco 1 's, entonces tiene un número par de 1's; si una cadena tiene cinco 1's o más, entonces contiene un número impar de 1's; cualquier cadena contiene al menos un 1" . El lenguaje L:

a) Es regular

b) Es independiente del contexto determinista y no es regular

c) Es independiente del contexto no determinista y no es regular









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

Primero reflexionemos sobre si puede ser regular (representable con autómata finito). Pensamos que quizás lo sea, por lo que vamos a intentar reflexionar y representarlo:

Cualquier cadena contiene al menos un 1 se puede expresar con un autómata finito.
Si una cadena tiene menos de cinco 1´s entonces tiene un número par de 1´s: podemos poner transiciones cuando se reciba un 1, y hacer que si se han recibido 2 ó 4 signos 1 se esté en aceptación. Al recibir un quinto 1 también estaríamos en aceptación y recibir 2 unos adicionales nos devuelven a la aceptación. Los ceros los admitimos en cualquier estado porque no se especifica nada.

Representación gráfica:

Hemos representado el lenguaje con un autómata finito, por tanto es un lenguaje regular y respondemos la opción a).

[nosferacento]

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.

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

[nosferacento]

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.

[nosferacento]

PREGUNTA: Dada la gramática G:

S -- > aS | bA | ε
A -- > bB | aS | ε
B -- > aB | bB

Indicar cuál de las siguientes expresiones regulares genera el mismo lenguaje que la gramática G:

a) a* (b(aa*b)*)*a

b) b(b(aa*b)*)*

c) (a + ba)*( ε + b)

d) Ninguna de las anteriores expresiones regulares genera el mismo lenguaje que la gramática G









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

Analizamos la gramática. Dado el símbolo inicial S, nos permite alcanzar la cadena vacía con lo cual ε forma parte del lenguaje.

El símbolo B es alcanzable pero en caso de utilizarlo no nos permite poner término a la recursión y terminar la cadena, con lo cual ignoraremos el símbolo B y pensaremos en la gramática como si fuera esta:
S -- > aS | bA | ε
A -- > aS | ε

Cualquier cadena que comience por a y tenga un número variable de a´s forma parte del lenguaje, es decir, a, aa, aaa, etc. como ε está incluido en el lenguaje podemos decir que a* forma parte del lenguaje.

La rama bA nos lleva a que: b esté incluida en el lenguaje. b puede venir seguida por un número indeterminado de a´s, lo que incluye ba*.

Desde bA podemos derivar a baS lo cual nos permite generar cadenas de tipo (ba)* y ba*

Cualquier cadena puede terminar en b si alcanzamos bA, y derivamos A a la cadena vacía.

Analizamos la opción a). Esta opción obliga a que la cadena termine con una a, lo cual excluye la cadena vacía. Por tanto la opción a) es falsa.

Analizamos la opción b). Esta opción obliga a que toda cadena empiece por b, lo cual excluye a la cadena a que sabemos forma parte del lenguaje. Por tanto la opción b) es falsa.

Analizamos la opción c, (a + ba)*( ε + b). Esta expresión permite que la cadena empiece por a y tenga cualquier número de a´s, correcto.

Según esta expresión ε está incluido en el lenguaje, correcto.

Según esta expresión b está incluida en el lenguaje, correcto. b puede venir seguida por un número indeterminado de a´s, lo que incluye ba*, correcto.

Esta expresión nos permite generar cadenas de tipo (ba)* y ba*, ya que ba puede seguirse de cualquier número de a´s, correcto.

La opción c) parece correcta, por lo que respondemos la opción c). No es una pregunta sencilla de responder.