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

[nosferacento]

Nota: He revisado las preguntas con vistas al curso 2023-2024 y en principio está todo "OK". De cualquier manera si encuentras alguna errata puedes escribirme tanto públicamente en el foro como por mensaje privado.

En este post se encuentran exámenes resueltos de la asignatura "Autómatas, gramáticas y lenguajes" de la UNED (Grado en Ingeniería Informática – Grado en Ingeniería de las Tecnologías de la Información), en general las preguntas son interesantes pero a veces te parecerán absurdas o rebuscadas. He incluido los exámenes "tal cual" para que puedas intentar resolverlos por tí mismo y comprobar la puntuación que hubieras obtenido.

He incluido tanto respuestas a las preguntas de los exámenes como algunos comentarios relativos a las prácticas. Los exámenes suelen consistir en un test de 10 preguntas. Tienen como dificultad añadida que las preguntas mal respondidas descuentan puntuación. Las prácticas aportan una fracción importante de la nota y consisten en una serie de ejercicios a resolver; aunque suelen consumir bastante tiempo de dedicación, conviene realizarlas para asentar conocimientos y no perder esa fracción de nota.

La mayoría de preguntas son de exámenes reales (de hecho corresponderán a los exámenes de los últimos años), en otros casos pueden ser inventadas. A través de los comentarios intentaré añadir pistas adicionales que ayuden a razonar las respuestas.

Otros post de interés para quienes busquen materiales:

Apuntes y recomendaciones para superar la asignatura "Fundamentos de Sistemas Digitales" del primer curso del Grado en Ingeniería Informática – Grado en Ingeniería de las Tecnologías de la Información de la UNED, que viene siendo una asignatura universitaria de introducción a la electrónica. Se pueden encontrar aquí: https://aprenderaprogramar.com/foros/index.php?topic=7066.0

Exámenes resueltos de la Asignatura "Fundamentos de sistemas digitales" del primer curso de Grado en Ingeniería Informática – Grado en Ingeniería de las Tecnologías de la Información de la UNED se puede encontrar aquí: https://www.aprenderaprogramar.com/foros/index.php?topic=6938.0

Exámenes resueltos de la Asignatura "Fundamentos de programación" del primer curso de Grado en Ingeniería Informática – Grado en Ingeniería de las Tecnologías de la Información de la UNED se puede encontrar aquí: https://www.aprenderaprogramar.com/foros/index.php?topic=401.0

Exámenes resueltos de la Asignatura "Programación orientada a objetos" del primer curso de Grado en Ingeniería Informática – Grado en Ingeniería de las Tecnologías de la Información de la UNED (lenguaje Java) se puede encontrar aquí: https://www.aprenderaprogramar.com/foros/index.php?topic=49.0

¡Gracias a todos los que envían comentarios y sugerencias!

[nosferacento]

PREGUNTA: Dado el lenguaje L = {xⁿyⁿ : n >= 0}, el lema de bombeo para los lenguajes regulares permite demostrar que:

a) No es posible construir un autómata finito que reconozca L

b) No es posible construir un autómata a pila que reconozca L

c) L es un lenguaje regular


RESPUESTA:

la opción correcta es la a).

El lema de bombeo para lenguajes regulares enuncia una propiedad que cumplen todos los lenguajes regulares infinitos. Si un lenguaje no cumple el lema de bombeo para lenguajes regulares se puede asegurar que dicho lenguaje no es un lenguaje regular (aunque el hecho de cumplir el lema de bombeo no asegura que el lenguaje es regular; en otras palabras, el lema de bombeo sirve para demostrar que un lenguaje no es regular, pero no para asegurar que un lenguaje sea regular)

Analizamos la opción b). El lema de bombeo para lenguajes regulares no trata sobre esto, por lo que directamente es falsa. Además si hemos hecho ejercicios nos daremos cuenta rápidamente de que el lenguaje propuesto es un lenguaje infinito que puede ser representado con un autómata a pila que va apilando con las x y desapilando con las y, para llegar a aceptación si la pila queda vacía (coincide el número de x con el número de ys). Por tanto la opción b) es falsa, el lema de bombeo para lenguajes regulares no permite demostrar eso y sí es posible construir un autómata a pila que reconozca L.

Analizamos la opción c). El lema de bombeo no permite demostrar que un lenguaje sea regular, por tanto es falsa. Además si fuera un lenguaje regular, tendría que ser reconocible por un autómata finito, pero con un autómata finito no se tiene la capacidad de contar, y aquí necesitamos contar el número de x y el número de ys. Por tanto la opción c) es falsa.

Ya por descarte podemos responder la a). Razonamos si es correcta: para reconocer este lenguaje es necesario poder contar el número de x y el número de ys, cosa que no puede hacer un autómata finito. Este lenguaje no cumple el lema de bombeo para lenguajes regulares y esto demuestra que no es posible construir un autómata finito que reconozca L. Por tanto la opción a) es correcta.

[nosferacento]

PREGUNTA:

Sea L el lenguaje que genera la siguiente gramática, donde S es el símbolo inicial de la gramática:

S --> 0S1 | A
A --> 1A0| S | λ

Indicar cuál de las siguientes afirmaciones es VERDADERA:

a) Existe un autómata a pila que reconoce L y que puede vaciar la pila antes de aceptar las cadenas
b) Existe una gramática en Forma Normal de Chomsky que genera L
c) Las dos afirmaciones anteriores son verdaderas



RESPUESTA:

La opción a responder es la a)

Nota: la cadena vacía la representaremos de cualquiera de estas maneras: λ, ɛ, lambda, épsilon

Sobre la opción b): una gramática en forma normal de Chomsky ha de cumplir 2+3 condiciones que son:

Primera y segunda: Toda producción ha de ser de tipo A -->BC con A, B y C variables ó
ha de ser de tipo A --> a donde A es variable y a un símbolo terminal

Tercera: No tiene producciones λ
Cuarta: no tiene producciones unitarias
Quinta: no tiene símbolos inútiles

Esta gramática tiene una producción lambda, en concreto A --> λ, por lo tanto no está en forma normal de Chomsky y la opción b) es falsa.

Ya podríamos responder la a) por descarte. De todas formas vamos a analizar el lenguaje. Lo primero es preguntarnos ¿genera λ el lenguaje? La respuesta es sí (esto es una cuestión importante cuando analizamos un lenguaje)

Ahora generaremos algunas cadenas para ver el comportamiento de la gramática:
S --> 0S1 --> 01
S --> 1A0 --> 10
S --> genera 00000… 11111 cualquier cadena con el mismo número de ceros que de unos

Vemos que el trabajo a realizar es contar mismo número de ceros que de unos, y esto lo puede realizar un autómata a pila.

Podemos "ver" que el lenguaje es 0ⁿ1ⁿ U 1ⁿ0ⁿ | n>=0, esto es una deducción no matemática, sino basada en la observación.

Ahora nos podemos plantear si existe un autómata a pila que reconozca esta gramática y que pueda vaciar la pila antes de aceptar las cadenas.

Una forma sencilla de representar una gramática con un autómata a pila es crear una transición inicial que no consume ningún carácter y pone el símbolo inicial de la gramática en la pila. En el estado que se alcanza ponemos las transiciones correspondientes a producciones de la gramática con λ como carácter de entrada y el símbolo correspondiente en la pila y la producción como elemento de reemplazo en la pila. Con esto representamos que cualquier sustitución es posible usando las producciones. Finalmente los símbolos terminales permiten ser consumidos sin modificar la pila, que se mantiene tal cual. Una transición espontánea permite acabar en aceptación, pero recordar que para que exista aceptación la cadena de entrada tendrá que haberse consumido completamente. Lo podemos representar así:

Podemos considerar el símbolo de final de pila Z en la primera y última transición si queremos (aquí no lo hemos considerado).

¿Este autómata acepta el mismo lenguaje que la gramática? Sí. Puedes probar a pasarle algunas cadenas para comprobarlo.

¿Puede vaciar la pila antes de aceptar la cadena? Sí

Luego la opción a) es verdadera.

Si te has perdido en alguna parte de la explicación posiblemente es porque te falte la base teórica o hacer más ejercicios, esta pregunta no puede considerarse sencilla pero tampoco excesivamente complicada.

[nosferacento]

PREGUNTA:

Si el estado inicial de un autómata a pila no es de aceptación, ¿Es posible que reconozca la palabra vacía?

a) No
b) Si


RESPUESTA:

La opción a responder es la b)

La palabra vacía o cadena vacía, λ ó épsilon, funciona como si se tratara de un carácter cuando hablamos de autómatas, gramáticas y lenguajes. Por tanto nos pregunta si un autómata a pila cuyo estado inicial no es de aceptación puede reconocer λ. La respuesta es obvia: sí.

Los lenguajes independientes del contexto son representables por gramáticas independientes del contexto y por autómatas a pila. A su vez, los lenguajes regulares representables mediante expresiones regulares y mediante autómatas finitos (deterministas o no deterministas) son un subconjunto de los lenguajes independientes del contexto. Podemos hacer varios razonamientos que nos llevan a la misma conclusión:

a)   λ es una expresión regular, por tanto es un lenguaje regular y es un LIC, por tanto se puede representar con un autómata a pila cuyo estado inicial no es de aceptación.
b)    λ puede ser aceptada por un AFD con un estado inicial de no aceptación que pasa al estado de aceptación al recibir λ. También se podrá representar con un autómata a pila.

Y lo más recomendable: dibuja el autómata a pila y compruébalo directamente. Lo dibujamos con un estado inicial “1” de no aceptación. Inicialmente la pila podemos considerar que contiene la señal de fin de pila Zo o no. Supongamos que no la contiene. La primera transición, al estado “2” sería λ, λ; Zo lo que significa que no consumimos ningún carácter, nos da igual lo que haya en la pila y ponemos en la cima Zo. La segunda transición, al estado de aceptación “3” sería λ, Zo; Zo que significa que si leemos la cadena vacía estando Zo como cima de pila, ponemos Zo como cima de pila (es decir, no hemos hecho nada más que leer la cadena vacía y pasar a aceptación).

También podíamos haberlo hecho directamente: del estado inicial, leer λ y pasar a aceptación. Tener en cuenta que λ es un símbolo especial ya que como carácter de entrada tiene el sentido de una transición "espontánea".

Esta pregunta es sencilla, casi diríamos que muy sencilla. La cuestión es que en ocasiones en los exámenes aparecen preguntas aparentemente sencillas pero después no lo son, por lo que siempre conviene pensar y repensar antes de responder. En este caso la pregunta parece sencilla y efectivamente es sencilla, no hay truco.

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

En relación a la opción a), ni autómatas finitos ni autómatas a pila tienen cabeza lectora (aunque sí pueden retroceder a estados ya visitados) por lo que es cierta

En relación a la opción b) las máquinas de Turing pueden escribir sobre su cinta (y pueden tener una o varias cintas), por lo que es cierta.

Por tanto respondemos la opción c). 

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

Los lenguajes independientes del contexto tienen una serie de propiedades que debemos conocer (al menos si queremos ser capaces de responder a preguntas como esta). Entre esas propiedades tenemos que:

- La unión de dos lenguajes independientes del contexto (LIC) da como resultado un lenguaje que también es un LIC.

- La concatenación de dos LIC genera un LIC.

- La clausura o estrella de kleene de un LIC es también un LIC.

- La clausara positiva (igual que la estrella de kleene pero una repetición o más, no admite cero repeticiones) de un LIC es también LIC.

- La reflexión de un LIC es también un LIC (reflexión de una cadena: esa misma cadena escrita en orden inverso)

¿Existe alguna operación entre dos LIC que no genere un LIC? Sí, la intersección de dos LIC no tiene por qué ser LIC, el complementario de un LIC no tiene por qué ser LIC y la diferencia de dos LIC no tiene por qué ser LIC (sin embargo, la intersección, complementario o diferencia de lenguajes regulares sí es regular)

[nosferacento]

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

S --> AAA | B
A --> aA | B
B --> λ

Indicar cuál de las siguientes afirmaciones es verdadera:

a) La cadena vacía no forma parte del lenguaje generado por la gramática
b) El lenguaje que genera la gramática es independiente del contexto no regular
c) El lenguaje que genera la gramática puede expresarse mediante la expresión regular: a*
d) Ninguna de las anteriores afirmaciones es verdadera




RESPUESTA: La opción correcta es la c)

S deriva a B y B deriva a λ, por tanto la cadena vacía sí forma parte del lenguaje y la opción a) es falsa.

¿Es un lenguaje regular? Si logramos expresar la gramática en forma de expresión regular o como autómata finito, habremos demostrado que es un lenguaje regular. Para ello en primer lugar vamos a hacer un análisis intuitivo de qué cadenas se generan a partir de la gramática.

S genera AAA y A genera λ; la concatenación de varias λ es simplemente λ.
AAA se puede derivar a aAλλ, aAaAλ ó aAaAaA. En la práctica S --> AAA es igual que S-->A debido a la forma que tiene la gramática. A --> aA nos permite construir cadenas de la forma a+ (una repetición o más de a). Como A también deriva a λ la segunda regla equivale a la expresión regular a*, cero o más repeticiones de a. Concluimos que el lenguaje que genera la gramática es a* y esto es una expresión regular, por tanto se trata de un lenguaje regular y la opción b) es falsa.

La opción c) es correcta como hemos deducido anteriormente.

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {a, b}, sea L el lenguaje que reconoce el siguiente autómata finito:

Indicar cuál de las siguientes gramáticas regulares con símbolo inicial S, genera el lenguaje L:

a) S --> bS l aS l ε , A --> aA l bB, B --> bS l ε
b) S --> bS l aA, A --> aA l bB, B --> bS l ε
c) S --> bS l aS l aA l ε , A --> aA, B --> bS l ε
d) Ninguna de las anteriores gramáticas genera L



RESPUESTA: la opción correcta es la d)

Analizamos la opción a. Las reglas que define son:
S --> bS (OK con el autómata, desde el símbolo inicial podemos leer b y volver a S)
S --> aS (NO CONCUERDA con el autómata, desde el símbolo inicial no podemos leer a y volver a S)
S --> ε
A --> aA
A --> bB
B --> bS
B --> ε

Analizamos la opción b). Las reglas que define son:
S --> bS (OK con el autómata)
S --> aA (OK con el autómata)
A --> aA (OK con el autómata)
A --> bB (OK con el autómata)
B --> bS (OK con el autómata)
B --> ε (OK con el autómata)
Todas las reglas están de acuerdo con lo que indica el autómata, pero falta una cosa para que esta gramática represente al autómata. Una regla que indique que el estado inicial es de aceptación que se representaría como S --> ε, al faltar esta regla la gramática no genera el lenguaje L.

Analizamos la opción c). Las reglas que define son:
S --> bS (OK con el autómata, desde el símbolo inicial podemos leer b y volver a S)
S --> aS (NO CONCUERDA con el autómata, desde el símbolo inicial no podemos leer a y volver a S)
S --> aA
S --> ε
A --> aA
B --> bS
B --> ε

Tras analizar todas las gramáticas propuestas, ninguna concuerda. Por tanto la opción correcta es la d), Ninguna de las anteriores gramáticas genera L

[nosferacento]

PREGUNTA: Dada la siguiente gramática, donde B 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 + 1)*
b) Las cadenas pertenecientes al lenguaje que genera la gramática deben tener al menos un símbolo 1
c) El lenguaje que genera la gramática es independiente del contexto no regular
d) Ninguna de las anteriores afirmaciones es verdadera



RESPUESTA:

Analicemos las opciones. La gramática tiene como símbolo inicial B (¡cuidado!, normalmente es S pero aquí nos dicen explícitamente que es B), por lo cual mejor la ordenamos de la siguiente manera:

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

Vemos que los símbolos A y S resultan inalcanzables, con lo cual son derivaciones que no podremos utilizar. B genera cualquier cadena de ceros combinados con unos, que es precisamente la expresión regular (0+1)*. Por tanto la opción a) es la correcta y se trata de un lenguaje regular y de una gramática regular.

La opción b) es falsa puesto que el lenguaje admite la cadena vacía y cadenas que solo contengan ceros, por lo tanto las cadenas no han de tener un símbolo 1 siempre.

La opción c) es falsa puesto que si el lenguaje se puede describir con una expresión regular se trata de una expresión regular.

La opción d) es falsa como consecuencia de lo anterior.

Esta pregunta es bastante básica, quien no sepa responderla tiene que estudiar más!

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {a, b}, sea L el lenguaje que reconoce el siguiente autómata:

Indicar cuál de las siguientes afirmaciones es VERDADERA:

a) L es independiente del contexto no regular
b) L puede generarse también mediante una gramática en Forma Normal de Chomsky
c) L contiene al lenguaje generado por la expresión regular a*
d) Ninguna de las anteriores afirmaciones es verdadera




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

Si analizamos el autómata propuesto, podemos comprobar que acepta ba* únicamente, ya que las cadenas que comienzan con a llevan a un estado de no aceptación e igualmente las cadenas que comienzan con bb llevan a no aceptación, y si una cadena contiene baaaa… y luego una b entra también en no aceptación. Por tanto se trata de un lenguaje regular ya que lo podemos representar mediante una expresión regular.

Conviene siempre preguntarnos: ¿acepta λ el lenguaje o autómata? Esta cuestión suele resultar relevante. Aquí la respuesta es que no, el lenguaje no acepta la cadena vacía. También conviene ponernos unos cuantos ejemplos de cadenas aceptadas. En nuestro caso b, ba, baa, baaa, baaaa, etc.

 La opción a) resulta falsa.
La opción b) alude a si el lenguaje puede generarse con una gramática en FNC. 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.

Este lenguaje lo podemos representar con la gramática:

S -- > bB
B -- > aB
B -- > λ

Esta gramática no está en FNC.

El lenguaje también se genera con la gramática:

S -- > bB
S -- > b
B -- > aB
B -- > a

Esta gramática cumple con las condiciones de la FNC (recordar que producción unitaria es de tipo A -- > B y no se considera unitaria una producción como A -- > a).
Por tanto la opción b es verdadera.

Analizamos la opción c). Esta opción resulta tentadora pues parece que “sí”, pero en realidad “no”. ¿Por qué? Hemos dicho que es importante preguntarse siempre por λ. En este caso a* genera λ mientras que el lenguaje no lo genera. Por tanto L no contiene el lenguaje generado por a*, si lo contuviera debería generar λ.

En base a los razonamientos anteriores, la opción d tampoco es verdadera.

Para responder a esta pregunta hemos de tener bien claro qué es una gramática en FNC y esto requiere de un poco de memoria y práctica con estos conceptos.

[nosferacento]

PREGUNTA: Sea el alfabeto Σ = {0, 1}. Dado el lenguaje L₁ = {0ⁿ1^m0ⁿ | n , m >= 0} y el lenguaje L₂ reconocido por el siguiente autómata a pila (Nota:se supone que inicialmente la pila del autómata está vacía. El conjunto de símbolos de pila es Γ = Σ U {a, Zo}. En el diagrama de transiciones, algunos arcos tienen una etiqueta en la que el segundo elemento es ε. En este caso 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.):

Podemos afirmar que:

a) L₁ = L₂
b) L₁ ⊂ L₂
c) L₂ ⊂ L₁
d) L₁ ≠ L₂   



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

Analizamos qué es lo que hace y qué lenguaje genera el autómata a pila propuesto. En primer lugar lee un 0 y pone en la pila el símbolo de fondo de pila. A continuación puede añadir tantos ceros como desee añadiendo el símbolo a a la pila. Por el momento está reconociendo 0000… y contando el número de ceros. A continuación puede leer un 1 y desapila una a. Puede seguir leyendo símbolos 1 y desapilando a hasta el momento en que encuentra el símbolo de final de pila, lee un 1 y pasa a aceptación. Por tanto el lenguaje que está aceptando es 0ⁿ1ⁿ con n>0
L₁ = 0ⁿ1^m0ⁿ
L₂ = 0ⁿ1ⁿ

Analizamos la opción a). ¿Son iguales? No, luego la descartamos
Analizamos la opción b). ¿Es L1 subconjunto de L2? No, luego la descartamos.
Analizamos la opción c). ¿Es L2 subconjunto de L1? Aquí tenemos que pensar un poco ¿Está contenido L2 dentro de L1? Las cadenas de L1 obligatoriamente tienen dos ceros, por tanto no contiene cadenas con un solo cero y L2 no es subconjunto de L1. Podemos plantearlo con un ejemplo: ¿la cadena de L₂ 01 es reconocida por el autómata de L₁? La respuesta es no, luego L₂ no es subconjunto de L₁.

Analizamos la opción d). Efectivamente L₁ es distinto de L₂. Esta es la opción correcta.

Nota: L1 es un LIC no regular representable con un autómata a pila determinista y L2 también.

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

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {a, b}, sea L el lenguaje que reconoce el siguiente autómata:

Indicar cuál de las siguientes afirmaciones es VERDADERA:

a) L contiene al lenguaje generado por la expresión regular ba*
b) L puede generarse también mediante una gramática en Forma Normal de Chomsky
c) L puede representarse mediante la expresión regular (ε + b) a*
d) Ninguna de las anteriores afirmaciones es verdadera




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

En primer lugar trataremos de ver qué cadenas genera el autómata. Para empezar hemos de tener en cuenta que el estado inicial es de aceptación por lo cual el autómata acepta la cadena vacía ε. También acepta b, que lleva al estado de aceptación q2. También acepta ba* ya que en q2 tenemos un lazo sobre el estado que admite cualquier repetición de a un número entre cero y n veces. No acepta ninguna otra cosa ya que el resto de transiciones llevan a un estado de no aceptación del que no se puede salir. Por tanto el autómata acepta ε, b, ba*.
La opción a) es verdadera, ba* está contenido en L, es decir, cualquier cadena de ba* pertenece a L.

La opción b) alude a si el lenguaje puede generarse con una gramática en FNC. 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.

Este lenguaje lo podemos representar con la gramática:

S -- > bB
B -- > aB
B -- > λ

Esta gramática no está en FNC, y cualquier gramática para representar este lenguaje requerirá una producción λ por lo que no estará en FNC y esta opción es falsa.

Hemos dicho que el autómata acepta ε, b, ba*. ¿L puede representarse mediante la expresión regular (ε + b) a* ? La respuesta es que no, ε + b significa “la cadena vacía ó b”. Si eligiéramos la cadena vacía y la concatenamos con a, significaría que se acepta la cadena a, y a no pertenece al lenguaje.

La expresión regular que representa al lenguaje es (ε + ba*) que implica que se acepta la cadena vacía o bien una b seguida de ninguna o un número indefinido de as.

La opción d) es falsa debido a lo expuesto anteriormente.

[nosferacento]

PREGUNTA: Dado el autómata finito definido mediante la siguiente tabla de transiciones:

Estado          0                  1                  -->A A B *B B A Indicar cuál de las siguientes afirmaciones es VERDADERA: a) El lenguaje que acepta este automáta finito se puede representar mediante la expresión regular (1 + 01 )*0 b) El autómata finito no puede reconocer cadenas de longitud mayor que 106 c) El autómata finito no puede reconocer cadenas que contengan dos unos consecutivos d) El lenguaje que acepta este autómata finito se puede representar mediante la expresión regular (0*10*1)*0*10* RESPUESTA: La opción correcta es la d). Vamos a representar el autómata para tener una visión de qué lenguaje reconoce. Ahora es fácil deducir la expresión regular del lenguaje que reconoce el autómata: 0*10* representa el flujo desde A hasta B Ahora esta expresión se puede repetir 0 ó más veces si aparece un 1 como intermediario: (0*10*) (1(0*10*))* Esta expresión representa que: el autómata comienza pudiendo recibir cero o muchos ceros, le ha de seguir un uno que lleva a aceptación y que puede seguir con cero o muchos ceros. Una vez en aceptación, si se recibe un 1 seguido de la misma cadena anterior, volvemos a aceptación, y este ciclo intermediado por un uno se puede repetir cero o muchas veces. Nota: a esta expresión no llegamos directamente, tenemos que irla escribiendo y probando cadenas y haciendo los pequeños ajustes necesarios hasta comprobar que esté correcta. Analizamos las posibles respuestas. La opción a) es falsa pues la expresión regular propuesta no acepta 100 mientras que el autómata propuesto sí lo acepta. La opción b) es falsa, un autómata con bucles puede reconocer cadenas de longitud infinita (no existe límite). La opción c) es falsa, pues el autómata reconoce 111 La opción d) no coincide con la expresión regular que nosotros hemos planteado, pero un autómata puede estar representado por más de una expresión regular. Analizamos la propuesta. Si nos fijamos es la misma expresión regular pero planteada en distinto orden. (0*10*1) representa el bucle desde el estado de aceptación hasta volver al estado inicial. Posteriormente se pueden añadir cero o muchos ceros, obligatoriamente un uno para volver a aceptación, y a continuación se admiten cero o muchos ceros. Esta expresión regular representa el lenguaje del autómata, luego es la opción correcta.

[nosferacento]

PREGUNTA: Dada la siguiente gramática, donde S 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*1 (0 + 1)*

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

c) Puesto que es una gramática independiente del contexto no existe ningún autómata finito que reconozca el lenguaje generado por la gramática




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

Hay que prestar atención a cuál es el símbolo inicial de la gramática, pues a veces no corresponde al símbolo que aparece en primer lugar. En este caso sí que corresponde, y es el símbolo S.

En primer lugar haremos un tanteo de las cadenas que son aceptadas.

Como A lleva a λ y B lleva a λ, la cadena mínima que puede ser aceptada es 1. Por tanto la cadena vacía no pertenece al lenguaje.

Como A permite recursiones añadiendo uno ó más ceros tenemos que son aceptadas las cadenas como 01, 001, 0001, 00001, 000…0001

B permite recursiones añadiendo ceros o unos, lo cual implica que se aceptan cadenas de la forma 10, 100, 1000, 1000…000, también de la forma 11, 111, 111, 1111, 111…1111

Como A puede anteceder a B se admiten cadenas de la forma 0110, 001100, 0000….1…000… y también 000…1…1111…

Esto aparenta ser un lenguaje regular. No se deduce de lo que hemos visto que sea necesario contar, lo que haría que no fuera regular sino lenguaje independiente del contexto. Si logramos expresar el lenguaje con una expresión regular habremos demostrado que es un lenguaje regular.

Comenzamos la construcción de la expresión: requerimos un 1 obligatorio que puede ir antecedido de cero o muchos ceros: 0*1 representa esto

Ahora tenemos que tener en cuenta que se pueden añadir cero o muchos ceros a la derecha, o cero o muchos unos a la derecha. La expresión queda:
0*1(0+1)*

Comprobamos que todas las cadenas que dedujimos sean representadas por la expresión regular. Efectivamente es así.

Analizamos las opciones posibles:
La opción a) es verdadera de acuerdo con el razonamiento que hemos seguido.

La opción b) ¿es verdadera? La verdad es que la expresión resulta muy similar a la primera, tan similar que podemos tener incluso la duda de si representa el mismo lenguaje. Para resolver esta duda tener en cuenta lo siguiente: cuando tenemos (0+1)* podemos poner unos delante de ceros, o ceros delante de unos. Cuando tenemos 0*1* si queremos poner ceros estos han de ir obligatoriamente delante de los unos, no podemos ponerlos detrás, opción que si tenemos con la otra forma. En este caso una cadena del lenguaje como 0110 no es representada por 0*10*1* porque el orden en esta expresión nos impide construir esta cadena. Por tanto esta opción es falsa, aunque no es fácil de ver.

Dado que hemos representado el lenguaje como expresión regular, existe un autómata finito que representa el lenguaje y la opción c) es falsa.

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {x,y,z}, sea L₁ = {xⁿyⁿzⁿ: n > 0} y sea L₂ el lenguaje reconocido por la siguiente máquina de Turing (Nota: Se supone que la máquina tiene el mismo alfabeto Σ y el conjunto de símbolos de cinta es r = Σ U {B} donde B representa el símbolo en blanco. Cuando analiza una cadena, la máquina de Turing parte de la configuración inicial donde la cinta de entrada contiene un símbolo en blanco seguido de la cadena a analizar seguida de blancos; la cabeza de lectura/escritura se encuentra situada en el primer símbolo a la izquierda de la cadena).

¿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 c. Nosotros nos decantamos por responder la c) (ver el razonamiento seguido a continuación)

En primer lugar reflexionamos sobre el lenguaje L1. ¿El lenguaje L1 es un lenguaje regular? No, ya que es necesario contar el número de apariciones de cada carácter y esta capacidad no la tienen los autómatas finitos. ¿Es un lenguaje independiente del contexto? Lo será si es reconocible por un autómata a pila. Nos inclinamos por pensar que sí es un LIC, ya que por cada x de entrada podemos apilar dos equis, luego con cada y desapilar una x y con cada z desapilar otra x llegando a aceptación.

Son cadenas que pertenecen a L1: xyz, xxyyzz, xxxyyyzzz, etc.


El lenguaje L2 que reconoce la máquina de Turing no sabemos cuál es. Sabemos que su alfabeto es x, y, z al igual que el de L1. No resulta sencillo saber qué lenguaje representa una máquina de Turing a primera vista. Nosotros vamos a optar por probar a pasarle cadenas de entrada y comprobar qué hace la máquina, y comparar lo que acepta o no acepta con lo que es aceptado en L1.

Vamos pasándole a la máquina de Turing cadenas y comprobamos qué sucede.

Pasando x, ó y, ó z no hay aceptación. Si nos fijamos en la máquina, para pasar de q0 a q1 requiere una x, para pasar de q2 a q3 requiere una y, y para pasar de q4 a q5 requiere una z. Además en cada estado tiene bucles que le permiten consumir más caracteres.

Pasamos xyz. La ejecución es: q0xyz   ├  q1Bxyz  ├  q2xyz  ├  xq2yz  ├  q3xyz  ├  q3Bxyz  ├ q4xyz  ├  xq4yz  ├  xyq4z  ├  xq5yz   llega a ACEPTACIÓN.

Pasamos xzy. La ejecución es: q0xzy  ├  q1Bxzy  ├  q2xzy  ├  xq2zy ├  xzq2y ├  xq3zy ├  q3xzy ├  q3Bxzy ├  q4xzy ├  xq4zy ├  q5xzy llega a ACEPTACIÓN   

Pasamos xxyz. La ejecución es q0xxyz  ├  q1Bxxyz  ├  q2xxyz  ├  xq2xyz  ├  xxq2yz  ├  xq3xyz  ├  q3xxyz  ├  q3Bxxyz  ├  q4xxyz  ├  xq4xyz  ├  xxq4yz  ├  xxyq4z  ├  xxq5z llega a ACEPTACIÓN

Pasamos xxyyzz. La ejecución es q0xxyyzz  ├  q1Bxxyyzz  ├  q2xxyyzz  ├  xq2xyyzz ├  xxq2yyzz  ├  xq3xyyzz  ├  q3xxyyzz  ├  q3Bxxyyzz  ├  q4xxyyzz  ├  xq4xyyzz  ├  xxq4yyzz  ├  xxyq4yzz  ├ xxyyq4zz  ├  xxyq5yzz llega a ACEPTACIÓN 

A la vista de los resultados (quizás algunas personas sean capaces de verlo más rápido, pero otras necesitaremos hacer estas pruebas para poder verlo) podemos decir que la máquina acepta cadenas que tengan al menos una x, una y y una z en cualquier orden sin necesidad de que estén balanceadas.

Podríamos alegar que en una cadena como xxyyzzzzz quedarán parte de las zetas sin inspeccionar, pero esto es algo propio de las máquinas de Turing. Las máquinas de Turing copian la cadena de inicio a la cinta y a partir de ahí trabajan con la cinta sin importarles la entrada, de ahí que puedan llegar a aceptación dejando parte de las cadenas sin inspeccionar.

Si tratamos de ver lo que hace la MT, 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.

Ahora analizamos las opciones.

a) ¿Son L1 y L2 iguales? No, L1 requiere balanceo y L2 no
b) ¿Son distintos? Lo dejamos pendiente
c) ¿Es L1 un subconjunto de L2?, es decir, ¿todas las cadenas de L1 están en L2? Esto equivale a decir, ¿todas las cadenas balanceadas son reconocidas por la máquina de Turing? La respuesta es sí
d) ¿Es L2 subconjunto de L1? Es decir, ¿dentro de L1 (insulto) cadenas no balanceadas? La respuesta es no.

La duda puede estar entre la opción b) y la c), ya que es verdad que son distintos y es verdad que L1 es subconjunto de L2. Esto en el examen podría comentarse (recomendamos hacerlo). Para responder, nos decantamos por la opción c) porque es la respuesta más precisa, pero recomendamos incluir una explicación al respecto en una hoja adicional.

[nosferacento]

PREGUNTA: Dado un alfabeto Σ, sea L un lenguaje independiente del contexto. Sea c(L) el complementario de L (esto es, c(L) = Σ* - L). Indicar cuál de las siguientes afirmaciones es VERDADERA:

a) Es posible que existan dos gramáticas en forma normal de Chomsky, una para L y otra para c(L)

b) Es imposible que existan dos gramáticas en forma normal de Chomsky, una para L y otra para c(L )

c) Es imposible que exista una gramática en forma normal de Chomsky ni para L ni para c(L)





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

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.

Si L contiene la cadena vacía, su complementario no la contendrá y por tanto no podrá expresarse en Forma Normal de Chomsky. Si por el contrario L sí contiene la cadena vacía entonces será c(L) quien no la contendrá y la que no podrá expresarse en Forma Normal de Chomsky. Como conclusión, no es posible que L y c(L) se puedan expresar ambos con gramáticas en FNC y la opción a) es falsa.

Por el mismo motivo, la opción b) es verdadera, o existe FNC para L ó existe para c(L), pero es imposible que exista para ambos.

La opción c) es falsa, no hay motivo para que sea imposible que exista una gramática en FNC para un LIC.

[nosferacento]

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

S --> SS | (S) | λ

Indicar cuál de las siguientes afirmaciones es VERDADERA:

a) Es una gramática regular y por tanto, el lenguaje que genera es regular

b) No es una gramática regular y por tanto, el lenguaje que genera nunca puede ser regular

c) El lenguaje que genera la gramática del enunciado es independiente del contexto no regular



RESPUESTA: La opción correcta es la c)

Analicemos cuáles son las cadenas que genera la gramática.

Se genera la cadena vacía λ

La regla (S) permite generar (S) -- > ((S)) -- > (((S))) … etc, y derivando S a la cadena vacía nos queda cualquier cadena de paréntesis balanceados, es decir, el mismo número de paréntesis de apertura que de cierre.

La regla SS permite derivar SS -- > (S)(S) -- > ((S))(S) -- > ((()))(), es decir, cualquier cadena de paréntesis balanceados concatenados con más paréntesis balanceados.

Para representar paréntesis balanceados con un autómata necesitamos contar el número de paréntesis de apertura y el número de paréntesis de cierre. Los autómatas finitos no tienen capacidad para contar (no pueden “recordar”), por lo que podemos afirmar que no se trata de un lenguaje regular. Por tanto la opción a) es falsa.
Respecto a la opción b), hay que tener en cuenta que hay muchos tipos de gramáticas y el hecho de que una gramática no sea regular no implica que no pueda generar un lenguaje regular, por tanto b) es falsa.

Respecto a la opción c), para representar el lenguaje se puede utilizar un autómata a pila que apile con paréntesis de apertura y desapile con paréntesis de cierre. Los autómatas a pila representan lenguajes independientes del contexto. Además este lenguaje es no regular como hemos visto. Por tanto la opción c) es cierta.

Nota: la opción b) puede generar ciertas dudas. La cuestión a tener presente es que una gramática regular siempre genera un lenguaje regular, pero hay gramáticas no regulares que pueden generar lenguajes regulares. Para ser gramática regular hay que cumplir ciertas normas. Hay gramáticas que se pueden saltar esas normas y aún así generar un lenguaje regular.

[nosferacento]

PREGUNTA: Dado el alfabeto Σ = {0, 1}, sea el lenguaje L = {0ⁿ1^m : n <= m}. Indicar cuál de las siguientes afirmaciones es VERDADERA:

a) Es posible construir un autómata a pila determinista que reconoce L

b) L es un lenguaje regular

c) Cualquier autómata a pila que reconozca L debe ser no determinista




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

Analizamos el lenguaje. El lenguaje comprende todas las cadenas con igual o menor número de ceros que de unos. No nos dice nada sobre cuál es el valor mínimo para n y m, por lo que supondremos que el valor mínimo es cero (no tendría sentido admitir números negativos). Con este supuesto, las cadenas admitidas comprenden: ε, 01, 0011, 000111 , 000…111… balanceados, así como 1, 11, 111, 1111, 11111… y también 011, 0111, 01111… etc.

El balanceado es posible pero no obligatorio. Vamos a tratar de expresarlo como lenguaje regular. 0*1* no garantiza que haya menor o igual número de ceros que de unos. Para garantizar esto necesitamos contar, y esto no lo pueden hacer los autómatas finitos, por lo tanto desechamos que sea un lenguaje regular.

Ahora consideremos la posibilidad de representar el lenguaje con un autómata a pila determinista. Empezaríamos en un estado q0 con una transición ε poniendo el símbolo de fin de pila Z en la pila. En un estado q1 leeríamos cualquier símbolo 0 y lo añadiríamos a la pila. Al leer un símbolo 1, pasaríamos a un estado q2 y desapilamos un cero. Por cada 1 leído en q2 desapilamos un cero. Si llega un momento en que la pila queda vacía (aparece Z) significa que al menos había tantos unos como ceros y con 1, Z; Z pasaríamos a un estado q3 donde consumimos todos los unos que puedan venir adicionalmente con transiciones 1, Z; Z. Cuando se terminen de consumir los unos una transición ε, Z; Z nos llevaría a q4 (aceptación). Este autómata es determinista (no tiene dos transiciones posibles para una entrada y símbolo de pila).

Su representación sería esta:

Por tanto:

La opción a) es verdadera.
La opción b) es falsa.
La opción c) es falsa. Quizás se pueda representar con un no determinista, pero no es cierto que cualquier autómata a pila deba ser no determinista para reconocer el lenguaje.

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