-
Nota: He revisado las preguntas con vistas al curso 2024-2025 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!
-
PREGUNTA: Dado el lenguaje L = {xnyn : 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.
-
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 0n1n U 1n0n | 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í:
(http://i.imgur.com/mReUKV4.png)
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.
-
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.
-
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).
-
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)
-
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.
-
PREGUNTA: Dado el alfabeto Σ = {a, b}, sea L el lenguaje que reconoce el siguiente autómata finito:
(http://i.imgur.com/irvFOog.jpg)
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
-
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!
-
PREGUNTA: Dado el alfabeto Σ = {a, b}, sea L el lenguaje que reconoce el siguiente autómata:
(http://i.imgur.com/c9MXmGY.jpg)
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.
-
PREGUNTA: Sea el alfabeto Σ = {0, 1}. Dado el lenguaje L1 = {0n1m0n | n , m >= 0} y el lenguaje L2 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.):
(http://i.imgur.com/mWQr6pR.jpg)
Podemos afirmar que:
a) L1 = L2
b) L1 ⊂ L2
c) L2 ⊂ L1
d) L1 ≠ L2
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 0n1n con n>0
L1 = 0n1m0n
L2 = 0n1n
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 L2 01 es reconocida por el autómata de L1? La respuesta es no, luego L2 no es subconjunto de L1.
Analizamos la opción d). Efectivamente L1 es distinto de L2. 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.
-
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...
-
PREGUNTA: Dado el alfabeto Σ = {a, b}, sea L el lenguaje que reconoce el siguiente autómata:
(http://i.imgur.com/U8fV8Ob.jpg)
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.
-
PREGUNTA: Dado el autómata finito definido mediante la siguiente tabla de transiciones:
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.
(http://i.imgur.com/qAD0cwt.png)
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.
|
-
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.
-
PREGUNTA: Dado el alfabeto Σ = {x,y,z}, sea L1 = {xnynzn: n > 0} y sea L2 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).
(http://i.imgur.com/aGNRBgJ.jpg)
¿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.
-
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.
-
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.
-
PREGUNTA: Dado el alfabeto Σ = {0, 1}, sea el lenguaje L = {0n1m : 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:
(http://i.imgur.com/XAhbeLJ.png)
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.
-
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.
-
PREGUNTA: Sea L el lenguaje definido por el conjunto de cadenas del alfabeto Σ = {a, b, c} que contienen al menos una a y al menos una b. Indicar cuál de las siguientes afirmaciones es VERDADERA:
a) L es un lenguaje independiente del contexto no regular
b) L es un lenguaje regular y por tanto, es posible encontrar una expresión regular que lo reconozca
c) La definición del lenguaje impone restricciones acerca del número de c's que deben contener las cadenas del lenguaje
RESPUESTA: la opción correcta es la b).
Vamos a tratar de plantear un autómata finito que represente el lenguaje. Si lo logramos, ya sabremos que es una expresión regular.
Partimos de un estado inicial q0. Si en dicho estado se lee una c, el autómata se mantiene en q0. Si se lee una a el autómata pasa al estado q1 y si se lee una b el autómata pasa al estado q2. Si estando en q1 se lee una c ó una a, el autómata permanece en q1, mientras que si se lee una b el autómata pasa al estado de aceptación q3. Si estando en q2 el autómata lee una b ó una c, el autómata permanece en q2, mientras que si lee una a pasa al estado de aceptación q3. En q3 la lectura de a, b ó c hacen que se permanezca en q3.
Si queremos estar más seguros lo dibujamos y lo probamos con diferentes cadenas.
Analizamos las opciones: a) es falsa porque dice que es un lenguaje no regular.
b) es verdadera pues como hemos visto es un lenguaje regular.
c) es falsa porque la definición del lenguaje no dice nada acerca del número de c´s que deben contener las cadenas del lenguaje.
-
PREGUNTA: Dada la siguiente gramática, donde A es el símbolo inicial de la gramática:
S -- > A1B
A -- > 0A | λ
B -- > 0B | 1B | λ
Indicar cuál de las siguientes afirmaciones es VERDADERA:
a) La gramática genera el lenguaje representado por la expresión regular 0*
b) La gramática genera el lenguaje representado por la expresión regular 0*1 (0 + 1)*
c) La gramática genera un lenguaje con un número finito de cadenas
d) Ninguna de las anteriores afirmaciones es verdadera
RESPUESTA: la opción correcta es la a)
Tenemos que prestar atención a cuál es el símbolo inicial de la gramática, normalmente S pero en este caso nos indican específicamente que es A. Por ello vamos a reescribir la gramática comenzando con la regla asociada al no terminal A para evitar confundirnos.
A -- > 0A | λ
B -- > 0B | 1B | λ
S -- > A1B
Al analizar la gramática con A como símbolo inicial vemos que B y S son símbolos inalcanzables, por tanto la gramática se reduce a esta regla: A -- > 0A | λ
Esta gramática es recursiva por la derecha y admite la cadena vacía λ dentro del lenguaje que genera. El lenguaje generado es λ, 0, 00, 000, 0000… que es lo mismo que la expresión regular 0*
Analizamos las posibles respuestas:
a) es verdadera
b) es falso, el símbolo 1 no aparece dentro del lenguaje
c) es falso, el número de cadenas que genera es infinito
d) es falso
Pregunta sencilla pero donde mucha gente cometerá la equivocación de usar S como símbolo inicial de la gramática. ¡Prestar atención!
-
Con las últimas diez preguntas hemos completado un examen, que normalmente consta de diez preguntas tipo test. Es conveniente que se trate de resolver el examen haciendo una simulación de examen real, controlando el tiempo empleado y respondiendo todas las preguntas a la vez sin consultar ningún tipo de documentación, y luego comprobar cómo nos hubiera ido en ese caso supuesto "real" y qué nota habríamos sacado. Para quien quiera intentarlo, dejo el examen con enunciados completos en el archivo adjunto a este post (archivo jun13_1a_sem_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...
-
PREGUNTA: Sea el lenguaje L = {xnymzn : con n y m > 0, y con n ≠ m}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?
a) Un autómata finito.
b) Un autómata a pila determinista.
c) Un autómata a pila no determinista.
d) Una máquina de Turing.
RESPUESTA: la opción correcta es la d).
El lenguaje implica que el número de x´s ha de ser igual al número de z´s, y con al menos una y entre las x´s y las z´s. El número de x´s y z´s tiene que ser distinto al número de y´s. El número mínimo de cualquier símbolo es 1.
Con estas premisas xyz no se acepta porque el número de y´s tiene que ser distinto que el número de x´s y de z´s. Se aceptarían las siguientes cadenas:
xyyz, xyyyz, xyyyyyy…yyyyyyz, xxyzz, xxxyzzz, xx…xxyzz..zz, xxxyyzzz, etc.
Necesitamos contar, con lo cual ya sabemos que los autómatas finitos no podrán representar este lenguaje.
Ahora nos preguntamos, ¿podrá un autómata a pila reconocer este lenguaje? Necesitamos comprobar las siguientes restricciones:
a) Que el número de z´s sea distinto al número de x
b) Que el número de x´s sea igual al número de z´s
c) Que tanto el número de x´s como de y´s sea al menos 1
Con un autómata a pila podemos contar algo añadiendo a la pila y comprobar la coincidencia con otra cosa desapilando, pero aquí esto no es suficiente, necesitaríamos contar dos cosas: las x´s y las y´s, luego desapilar con las z´s y verificar que las x´s están en distinto número que las y´s. Esta capacidad de computación podríamos decir que necesita “2 pilas” y está por encima de las posibilidades de un autómata a pila, sea determinista o no determinista, por lo que concluimos que la máquina más simple para reconocer este lenguaje ha de ser una máquina de Turing.
Otra vía para tratar de responder esta pregunta es usar el lema de bombeo para lenguajes independientes del contexto. El lenguaje xny2nzn sería un subconjunto del lenguaje y por tanto debería ser un LIC si el lenguaje propuesto fuera un LIC. Supongamos que este lenguaje es un LIC. Entonces existe un valor constante n de forma que para z = xny2nzn se cumpliría que:
z = uvwxy
|vwx| <= n
v ≠ λ, x ≠ λ
Si |vwx| <= n significa que vwx ha de estar formado en nuestro caso por símbolos y´s, mientras que x ha de contener símbolos x´s y posiblemente y´s , y z ha de estar formado posiblemente por símbolos y´s y por símbolos z´s.
Según el lema de bombeo uvkwxky ha de pertenecer al lenguaje para todo k>=0, pero si hacemos k=0 tenemos que la parte central de la cadena estaría formada por como mucho n símbolos y, mientras que necesitamos 2n símbolos y. La cadena no pertenecería al lenguaje y no se cumple el lema de bombeo para lenguajes LIC, por lo que podemos concluir que el lenguaje no es un LIC.
Conclusión: será necesaria una máquina de Turing para reconocer el lenguaje.
Esta pregunta es menos simple de lo que parece.
-
PREGUNTA: El lema del bombeo aplicado a los lenguajes regulares nos demuestra que para todo autómata finito no determinista existe un autómata finito determinista que reconoce el mismo lenguaje.
a) Verdadero.
b) Falso.
RESPUESTA: la opción correcta es la b). El lema de bombeo aplicado a los lenguajes regulares nos demuestra que si un lenguaje no cumple el lema de bombeo no es un lenguaje regular. En caso de cumplirse, no es garantía de que el lenguaje sea regular ni de que no lo sea. No tiene nada que ver con lo que indica el enunciado de la pregunta, por lo tanto la respuesta es la b), Falso.
-
PREGUNTA: Dado el lenguaje L = {xnym : n, m > 0} definido por la gramática
S -- > xX
X -- > xX
X -- > yY
Y -- > yY
Y -- > λ
¿Podríamos construir su forma normal de Chomsky?
a) Si.
b) No.
RESPUESTA: la opción correcta es la a).
Recordar que la FNC implica estas condiciones:
a) El lenguaje no genera la cadena vacía
b) Toda producción es de tipo A -- > BC ó A -- > a
c) La gramática no tiene producciones λ ni producciones unitarias ni símbolos inútiles.
¿Genera este lenguaje la cadena vacía? S ha de derivar en xX. Dado que X ha de derivar en xX ó yY llegamos a xxX ó xyY. Si derivamos Y a la cadena vacía tenemos que la cadena más corta que se puede generar es xy. Por tanto el lenguaje no contiene la cadena vacía.
Nota: puede despistar el que haya una producción que lleve a la cadena vacía, pero esto no significa que el lenguaje genere la cadena vacía.
Vamos a intentar ponerla en forma normal de Chomsky. Para ello en primer lugar eliminamos las producciones λ. Reemplazamos las producciones λ haciendo el reemplazo por todas las producciones alternativas posibles. La gramática queda:
S -- > xX
X -- > xX
X -- > y
Y -- > yY
Y -- > y
En segundo lugar eliminaríamos producciones unitarias tipo A -- > B pero como no tenemos pasamos al siguiente paso.
En tercer lugar eliminaríamos símbolos inútiles pero como no tenemos pasamos al siguiente paso.
Nos falta dejar la gramática en la forma adecuada. Para ello introducimos variables adicionales como F -- > x así como G -- > y. La gramática queda:
S -- > FX
X -- > FX
F -- > x
X -- > y
Y -- > GY
Y -- > y
G -- > y
Esta gramática está en forma normal de Chomsky y genera el mismo lenguaje que la gramática inicial, por tanto la respuesta es la a), sí se puede construir la FNC.
-
PREGUNTA: Dado el lenguaje L definido por la siguiente gramática:
S -- > xX
S -- > Sy
S -- > xy
L es reconocido por el siguiente automáta a pila:
(http://i.imgur.com/HGwYkMP.jpg)
Podemos asegurar que el lenguaje es un lenguaje independiente del contexto no regular
a) Verdadero.
b) Falso.
RESPUESTA: La opción correcta es la opción b).
Veamos cadenas que genera el lenguaje: no se admite la cadena vacía. Genera: xy, xxy, xxxy, xxx…xxxy, xyy, xyyy, xyyy…yyy, xxx…xxxxyyyy…yyy
El lenguaje permite tantas x antes y tantas y después como se quiera, obligando a que aparezca una xy central.
Vamos a tratar de encontrar una expresión regular que describa el lenguaje: x*(xy)y* permite que haya tantas x antecesoras como se quiera, obliga a que haya una xy central y permite tantas y posteriores como se quiera. También podemos escribir el lenguaje como xx*yy*. Además si nos fijamos en el autómata a pila propuesto, podemos transformarlo en un autómata finito determinista que parte de qo y pasa a q1 cuando recibe una x, admite tantas x como se desee en q1 mediante un lazo y pasa a q2 (aceptación) al recibir una y. Además en q2 admite tantas y como se desee mediante un lazo.
Por tanto se trata de un lenguaje regular, con lo cual es falso que sea un lenguaje independiente del contexto no regular. Respondemos la opción b).
Nota: el hecho de que el lenguaje se describa con un autómata a pila tal y como se plantea en el enunciado significa que es un LIC, pero no dice nada respecto de si el lenguaje es regular o no regular ya que los lenguajes regulares son un subconjunto de los LIC.
-
PREGUNTA: Dado el lenguaje L1 = {xnyn : n > 0} y el lenguaje L2 = {xny2n : n > 0}.
a) El lenguaje L = L1 ∩ L2 no es reconocido por un autómata finito.
b) El lenguaje L = L1 ∩ L2 no es reconocido por un autómata a pila determinista.
c) El lenguaje L = L1 ∩ L2 no es reconocido por un autómata a pila no determinista.
d) Ninguna de las anteriores
RESPUESTA: la opción correcta es la d)
el lenguaje L1 comprende las cadenas: xy, xxyy, xxxyyy … siendo reconocible por un autómata a pila al que le basta apilar x´s y desapilarlas con y´s hasta vaciar la pila.
El lenguaje L2 comprende las cadenas xyy, xxyyyy, xxxyyyyyy … siendo reconocible por un autómata a pila al que le basta apilar dos x´s cada vez que reciba una x y desapilar una x cada vez que reciba una y hasta vaciar la pila.
Por tanto, L1 y L2 son lenguajes independientes del contexto. Ahora nos preguntan acerca de la intersección de estos dos lenguajes, es decir, el lenguaje que representa las cadenas comunes entre ambos. Sin embargo, ambos lenguajes no tienen cadenas en común (prueba a buscar alguna y verás que no hay), con lo que el lenguaje intersección es el lenguaje vacío. El lenguaje vacío es reconocido por cualquier autómata que simplemente tiene un estado de aceptación y no tiene transiciones. Por tanto, sí es reconocido por un autómata finito, a pila determinista o a pila no determinista, lo que hace las respuestas a), b) y c) falsas. Respondemos por tanto la opción d).
-
PREGUNTA: ¿Es posible construir la forma normal de Chomsky de la gramática siguiente?
S -- > AB
A -- > aAc
A -- > λ
B -- > bBc
B -- > λ
a) Si.
b) No.
RESPUESTA: la opción correcta es la b).
El símbolo inicial, dado que no nos indican otra cosa, es S. Con la producción S -- > AB podemos alcanzar la cadena vacía, ya que A deriva a la cadena vacía y B deriva a la cadena vacía. Por tanto, la cadena vacía forma parte del lenguaje generado por la gramática.
Recordar que la FNC implica estas condiciones:
a) El lenguaje no genera la cadena vacía
b) Toda producción es de tipo A -- > BC ó A -- > a
c) La gramática no tiene producciones λ ni producciones unitarias ni símbolos inútiles.
En este caso el lenguaje genera la cadena vacía por lo que respondemos la opción b), no es posible generar la forma normal de chomsky de esta gramática.
Nota: si se nos preguntara, ¿es posible generar una gramática que genere un lenguaje igual al lenguaje de esta gramática, excluida la cadena vacía, en forma normal de chomsky? La respuesta sería que podríamos responder que sí siguiendo el siguiente proceso (indicado a continuación PARA QUIEN LE INTERESE HACERLO COMO EJERCICIO). Primero, eliminar las producciones que llevan a la cadena vacía:
S -- > AB
S -- > A
S -- > B
A -- > aAc
A -- > ac
B -- > bBc
B -- > bc
Segundo, eliminar las producciones unitarias. Para ello se utiliza el método de pares unitarios:
(S, S) | (S, A) | (S, B)
(A, A)
(B, B)
S -- > AB | aAc | ac | bBc | bc
A -- > aAc | ac
B -- > bBc | bc
Hacemos estos cambios: X -- > a, Y -- > b, Z -- > c con lo que la gramática queda:
S -- > AB | XAZ | XZ | YBZ | YZ
A -- > XAZ | XZ
B -- > YBZ | YZ
Nos faltaría transformar las producciones que contienen tres no terminales en producciones con 2 no terminales. Para ello hacemos T -- > AZ, M -- > BZ y la gramática queda:
S -- > AB | XT | XZ | YM | YZ
A -- > XT | XZ
B -- > YM | YZ
T -- > AZ
M -- > BZ
Que ya está en forma normal de chomsky y representa el lenguaje inicial excepto la cadena vacía, es decir, L – { λ }
-
PREGUNTA: Sea el lenguaje L = {xnymzn : con n > 0 y m par}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?
a) Un autómata finito.
b) Un autómata a pila determinista.
c) Un autómata a pila no determinista.
d) Una máquina de Turing.
RESPUESTA: la opción correcta es la b).
Planteamos en primer lugar ejemplos de cadenas que pertenecen al lenguaje. El lenguaje no admite la cadena vacía. Admite xyyz, xyyyyz, xyy..yyz, x…xyy…yyz…z. Al hacer la referencia m par podemos preguntarnos si el 0 es considerado par. Vamos a considerar que sí. El cero cumple con la definición de número par: es un entero múltiplo del dos, 0 × 2 = 0. Entonces la cadena xz también sería admitida, así como xxyy, xxxyyy, etc.
Para reconocer este lenguaje podríamos apilar x´s y desapilar y´s, lo cual puede ser realizado por un autómata a pila. Sin embargo, adicionalmente necesitamos verificar que el número de y´s sea par. Esto podríamos hacerlo con un autómata a pila que apila con cada y que recibe y desapila con la siguiente. Vamos a tratar de representar el autómata. Primero lo dibujamos de forma aproximada y luego lo vamos perfeccionando a medida que vamos haciendo pruebas.
Para permitir la posibilidad de que vengan y´s o no vengan y´s podríamos pensar en usar no determinismo (transiciones basadas en la cadena vacía, “espontáneas”), pero tenemos que estudiar si podemos evitar el no determinismo. Vamos a intentarlo, puesto que la máquina determinista es más simple que la no determinista.
(http://i.imgur.com/7RgGg1X.png)
Ahora le pasamos las cadenas al autómata y comprobamos el comportamiento:
xz: acepta
xxzz: acepta
xx…xxzz…zz: acepta
xyyz: acepta
xyyyyz: acepta
xxyyzz: acepta
Conclusión: podemos reconocer el lenguaje con un autómata a pila determinista y la respuesta correcta es la b).
Nota: la posibilidad de un autómata finito la descartamos desde el momento en que necesitamos contar para reconocer el lenguaje.
Nota: este ejercicio quizás se pueda resolver de forma intuitiva teniendo en cuenta que las x´s se pueden contrarrestar con las z´s y que las y´s al ser pares se pueden contrarestar a sí mismas. No obstante, consideramos preferible representar el autómata y hacer comprobaciones antes que basarnos en una visión rápida.
-
PREGUNTA: Sea el lenguaje L definido por la gramática
S -- > AB
A -- > aAc
A -- > λ
B -- > bBc
B -- > λ
¿Cuál es la máquina más simple que puede reconocer este lenguaje?
a) Un autómata finito.
b) Un autómata a pila determinista.
c) Un autómata a pila no determinista.
d) Una máquina de Turing.
RESPUESTA: la opción correcta es la b).
Analicemos qué cadenas genera la gramática.
El símbolo inicial, dado que no nos indican otra cosa, es S. Con la producción S -- > AB podemos alcanzar la cadena vacía, ya que A deriva a la cadena vacía y B deriva a la cadena vacía. Por tanto, la cadena vacía forma parte del lenguaje generado por la gramática.
Las producciones A nos permiten generar cadenas con el mismo número de a´s que de c´s, por ejemplo ac, aacc, aaaccc, etc.
Las producciones B nos permiten generar cadenas con el mismo número de b´s que de c´s, por ejemplo bc, bbcc, bbbccc, etc.
La producción AB permite que se puedan concatenar cero o muchos pares de (ac) con cero o muchos pares de (bc).
Vamos a tratar de escribir una expresión regular que represente el lenguaje:
(ac)*(bc)*
¿Esta expresión regular representa el lenguaje? (incluido la cadena vacía). La respuesta es que no, esta expresión regular permite cadenas como ac, acac, acacac … ó bc, bcbc, bcbcbc… o la concatenación de ambas, pero esto no es el lenguaje que queremos representar.
Si nos fijamos necesitamos contar el número de a´s y verificar que el número de c´s que vengan a continuación sea igual, ó contar el número de b´s y verificar que el número de c´s que venga a continuación sea igual. Si necesitamos contar vamos a necesitar al menos un autómata a pila. Vamos a tratar de construir un autómata a pila que reconozca el lenguaje.
Podríamos pensar en este autómata, pero la transición λ desde q1 introduce no-determinismo.
(http://i.imgur.com/tEcoko8.png)
Para hacerlo determinista eliminamos la transición con cadena vacía desde q1 y a cambio hacemos q0 estado de aceptación.
(http://i.imgur.com/eSvdACS.png)
Con este autómata tenemos el problema de que obliga a recibir al menos ac una vez, mientras que el lenguaje permite que ac aparezca cero o muchas veces.
Vamos a corregir esto y redibujar el autómata:
(http://i.imgur.com/YGi4Ksu.png)
Ahora parece que sí está correcto. Es un autómata a pila determinista. Le pasamos cadenas:
λ : acepta
ac: acepta
aacc: acepta
aaa…ccc… : acepta
Nota: el autómata ha resultado relativamente complejo debido a la cantidad de variantes que admite. ¿Podíamos haber respondido sin dibujar el autómata? Posiblemente sí, teniendo en cuenta que el autómata “simplemente” tiene que apilar y desapilar en dos etapas puede “intuirse” que es un autómata a pila determinista, pero esto depende de “la capacidad de visión” que tenga cada uno. Esta pregunta es menos sencilla de lo que parece...
-
PREGUNTA: Dado el lenguaje L = {xnynzm : donde se cumplen las siguientes condiciones, n > 0, si n es par m es igual a 2 o si n es impar m es igual a 3}
¿Cuál es la máquina más simple que puede reconocerlo?
a) Un autómata finito
b) Un autómata a pila determinista
c) Un autómata a pila no determinista
d) Ninguna de las anteriores
RESPUESTA: la opción correcta es la b).
Veamos algunas de las cadenas que reconoce el lenguaje:
Con n=1, n es impar, reconoce xyzzz
Con n=2, n es par, reconoce xxyyzz
Con n=3, n es impar, reconoce xxxyyyzzz
Con n=4, n es par, reconoce xxxxyyyyzz
Con n=5, n es impar, reconoce xxxxxyyyyyzzz
Necesitamos contar las apariciones de las x´s para luego comprobar que las apariciones de las y´s sean coincidentes en número. Desde el momento en que necesitamos contar descartamos los autómatas finitos, requeriremos como mínimo un autómata a pila. En este caso, si logramos diferenciar cuándo el número de x´s es impar, sabemos que podemos llegar a aceptación desapilando las x´s y añadiendo dos z´s. Si logramos diferenciar cuándo el número de x´s es par, sabemos que podemos llegar a aceptación desapilando las x´s y añadiendo tres z´s.
Vamos a tratar de plantear un autómata a pila que resuelva el problema. A priori no tenemos del todo claro si va a ser posible resolverlo con un autómata a pila determinista o no. Después de varias pruebas y tanteos planteamos el siguiente autómata:
(http://i.imgur.com/FIRRoYw.png)
Este es un autómata a pila determinista. Pasamos las cadenas que habíamos planteado a este autómata. Vemos que las resuelve bien, y vemos que la generalización no plantea problemas. Hemos representado el lenguaje con un autómata a pila determinista, por tanto la opción correcta es la b).
Nota: el autómata resuelve bien porque logra diferenciar par / impar mediante transiciones y porque una vez detectado si el caso es par o impar tiene que añadir un número finito de símbolos.
Los estados se pueden interpretar de la siguiente manera:
q2: se ha reconocido un número impar de x´s
q3: se ha reconocido un número par de x´s
q6: se acepta la cadena de entrada
-
PREGUNTA. Sea el lenguaje L = {xnymzn : con n y m > 0, y con n = m}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?
a) Un autómata finito.
b) Un autómata a pila determinista.
c) Un autómata a pila no determinista.
d) Una máquina de Turing.
RESPUESTA: la opción correcta es la d).
Al indicarnos que n = m el lenguaje es equivalente a xnynzn : con n > 0, es decir, cadenas con el mismo número de x´s, y´s y z´s que aparecen en este orden. Un autómata finito no puede recordar el número de x´s que han aparecido para compararlo con el número de y´s y el número de z´s. Con un autómata finito podríamos reconocer ciclos simples xyz pero no cadenas del tipo xxxyyyzzz donde necesitamos recordar los caracteres que han aparecido previamente.
Pensemos ahora en un autómata a pila. Podríamos pensar en apilar con las x´s, luego desapilar con las y´s, pero ya no podríamos comprobar las z´s.
Supongamos ahora que apilamos dobles x´s cada vez que encontramos una x, luego hacemos una transición a otro estado al encontrar una y y desapilamos una x simple por cada y, luego hacemos una transición con una z a otro estado y desapilamos una x simple por cada z. Una cadena como xxyyzz nos llevaría a aceptación pero una cadena como xxyzzz también porque no sabemos al desapilar con las z´s quién ha puesto el símbolo, si se debe a una x ó se debe a una y.
Un autómata a pila no determinista nos permite explorar múltiples vías, pero tampoco nos permite recordar la información que necesitamos recordar.
Una máquina de Turing con varias cintas puede almacenar la información que desee (y puede reducirse a una máquina de Turing de una cinta si se quiere). Por tanto respondemos la opción d) Máquina de Turing.
-
Con lo visto hasta ahora hemos completado un examen, que normalmente consta de diez preguntas tipo test. Es conveniente que se trate de resolver el examen haciendo una simulación de examen real, controlando el tiempo empleado y todas las preguntas a la vez sin consultar ningún tipo de documentación, y luego comprobar cómo nos hubiera ido en ese caso supuesto "real" y qué nota habríamos sacado. Para quien quiera intentarlo, dejo el examen con enunciados completos en el archivo adjunto a este post (archivo jun12_2a_sem_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...
-
PREGUNTA: Dada la siguiente gramática regular no determinista, donde A es su símbolo inicial:
A -- > xA
A -- > yA
A -- > xB
B -- > xA
B -- > yA
B -- > xB
B -- > xC
C -- > yD
C -- > xB
D -- > λ
D -- > xB
D -- > yA
Podemos construir un autómata finito determinista con solo 2 estados que reconozca el mismo lenguaje.
a) Verdadero.
b) Falso.
RESPUESTA:
Tenemos que prestar atención al enunciado:
a) Nos dice que es una gramática regular no determinista con símbolo inicial A
b) Nos pregunta si podemos construir un autómata finito determinista que reconozca el mismo lenguaje
Por tanto no nos pide ni siquiera transformar la gramática en un autómata, sino ver si podemos construir un autómata que reconozca el mismo lenguaje.
Lo primero que haremos será reflexionar sobre el lenguaje y las cadenas que genera el lenguaje.
Si transformamos la gramática en autómata finito no determinista obtenemos esto:
(http://i.imgur.com/foLHMzp.png)
Este autómata finito es indeterminista, pero sabemos que un AFN se puede transformar en un AFD. Ahora trataremos de encontrar algunas de las cadenas aceptadas por el autómata:
xxy: es la cadena más corta que acepta, podríamos representarla con un AFD de dos estados, uno inicial que acepta indefinidamente x y otro final al que se llega con una y. Sin embargo, aparte de ser la cadena más corta que acepta es la secuencia final obligatoria para llegar a aceptación y se permiten expresiones del tipo x(intercarlar x´s e y´s)xxy. Si usamos un estado inicial que acepta indefinidamente x´s e y´s que nos lleve a aceptación con una y, no podemos asegurar que el final será xxy. Para asegurar este final, con un AFD necesitaremos más de dos estados.
Respondemos entonces b) Falso.
Otro razonamiento: cuando se pasa de AFD a AFN se definen nuevos estados a partir del conjunto potencia de los estados del AFN. En el paso de AFD a AFN nos podemos encontrar:
a) Caso peor: se generan 2n estados en el AFD
b) Caso mejor: se mantienen los n estados del AFN
Por tanto el AFD no tendrá menos de 4 estados y respondemos la opción b) Falso.
Aunque con lo dicho ya no es necesario, vamos a construir el AFD usando la técnica de subconjuntos a modo de ejercicio. Para ello partimos del estado inicial y vamos representando los conjuntos de estados alcanzables (y las transiciones desde cada uno de ellos) mediante cierres ε. En este caso como no tenemos transiciones ε simplemente tenemos que fijarnos en los estados alcanzables directamente en base al símbolo leído.
| | Estado | x | y | Observaciones |
| | {A} | {A, B} | {A} | Estado inicial |
| | {A, B} | {A, B, C} | {A} | |
| | {A, B, C} | {A, B, C} | {A,D} | |
| | {A, D} | {A, B} | {A} | De aceptación |
Nos queda este autómata:
(http://i.imgur.com/UxYKANU.png)
En este caso estamos en el caso “mejor”: no se ha incrementeado el número de estados respecto del AFN.
-
PREGUNTA: El lema del bombeo aplicado a los autómatas a pila demuestra que el lenguaje L = {xnynzn : n > 0} no puede ser reconocido por ninguna máquina.
a) Verdadero.
b) Falso.
RESPUESTA: la opción correcta es la b).
Falso. Este lenguaje puede ser reconocido por una máquina de Turing. El lema de bombeo aplicado a los autómatas a pila demuestra que un lenguaje no es un LIC, y por tanto no puede ser reconocido por un autómata a pila, pero no demuestra que un lenguaje no pueda ser reconocido por ninguna máquina.
-
PREGUNTA: Dado el lenguaje L1 reconocido por el autómata
(http://i.imgur.com/OXzYeJy.jpg)
y el lenguaje L2 definido por la gramática
S -- > xSy
S -- > λ
Podemos afirmar:
a) L1 = L2
b) L1 ≠ L2
c) L1 ⊂ L2
d) L2 ⊂ L1
RESPUESTA: la opción correcta es la b)
Hay que tener en cuenta que la gramática, lenguaje L2, obliga a que por cada x se añada una y, es decir, obliga a que el número de x y el número de y sean iguales. En cambio el lenguaje L1 permite que venga cualquier número de x y cualquier número de ys sin necesidad de que sean iguales. El lenguaje L1 está representado por un autómata finito determinista, por tanto es un lenguaje regular.
El lenguaje L2 será L2 = {xnyn | n >= 0}. Este lenguaje requiere contar el número de x para verificar que el número de y´s sean iguales. Los autómatas finitos no tienen capacidad para contar. Por tanto este lenguaje necesita de un autómata a pila para apilar con las x y desapilar con las y´s y se trata de un LIC.
Vemos que el lenguaje L2 se diferencia además de L1 en que L1 no acepta la cadena vacía y L2 sí acepta la cadena vacía.
Por tanto la opción a) es falsa: no son lenguajes iguales.
La opción b) significa que los lenguajes son distintos, lo cual es cierto pero vamos a repasar las otras opciones.
La opción c) significaría que todas las cadenas de L1 pertenecen a L2. ¿Es cierto? No, porque en L1 estaría por ejemplo xxxy que no está en L2 por no coincidir el número de x con el número de ys.
La opción d) significaría que todas las cadenas de L2 estarían en L1, lo cual no es cierto porque la cadena vacía no está en L1.
Respondemos la opción b), son lenguajes distintos. No es difícil de ver pero requiere razonar meticulosamente y sin perder de vista detalles como la aceptación o no de la cadena vacía.
-
PREGUNTA: ¿Existe algún lenguaje independiente del contexto no regular compuesto por un número finito de palabras?
a) Sí.
b) No.
RESPUESTA: la opción correcta es la b)
Si el lenguaje estuviera compuesto por un número finito de palabras sería representable por un autómata finito y por tanto sería un lenguaje regular. Para ser un LIC no regular debe admitir infinitas palabras, por tanto respondemos la opción b).
Adicionalmente indicaremos que: todo lenguaje con un número finito de palabras es regular. Es cierto que con muchas palabras quizás nos salieran autómatas finitos gigantescos, pero seguiría siendo un lenguaje regular.
-
PREGUNTA: Sea L2 = {xnynzn | n > 0}. Y sea L1 el lenguaje reconocido por la siguiente máquina de Turing.
(http://i.imgur.com/83y2hFz.png)
¿Cuál de las siguientes afirmaciones es correcta?
a) L1 = L2
b) L1 ≠ L2
c) L1 ⊂ L2
d) L2 ⊂ L1
RESPUESTA: hay dos opciones que podrían considerarse correctas, la b y la d. Nosotros nos decantamos por responder la d) (ver el razonamiento seguido a continuación)
Nota: fijarse que el símbolo B o blanco de la máquina de Turing aquí lo representan con un espacio vacío. Es decir, la transición de q1 a q2 es B;B, -->, etc. En otras ocasiones también se representa con un cuadradito vacío.
Tratemos de ver qué es lo que hace la máquina de Turing propuesta. Vemos que en la transición de q0 a q1 requiere una x, en la transición de q2 a q3 requiere una y, y en la transición de q4 a q5 requiere una z.
Nos preguntamos ¿admite la MT la cadena zyx? Para esta cadena tenemos estas transiciones: q0zyx ├ zq0yz ├ zyq0x ├ zq1yx ├ q1zyx ├ q1Bzyx ├ q2zyx ├ zq2yx ├ q3zyx ├ q3Bzyx ├ q4zyx ├ q5Bzyx
Efectivamente la máquina admite esta cadena. La máquina parece admitir cualquier cadena que contenga al menos una x, una y y una z sin requerir un orden específico.
Si tratamos de ver lo que hace, en primer lugar se mueve a derechas hasta encontrar una x. Luego vuelve al principio de la cadena, hasta encontrar el blanco inicial. Luego se mueve a derechas hasta encontrar una y, y seguidamente vuelve al principio de la cadena, hasta encontrar el blanco inicial. Luego se mueve a derechas hasta encontrar una z y acepta.
Hemos visto que admite zyx y esta cadena no pertenece al lenguaje L2, por tanto descartamos tanto la opción de que L1 = L2 como la opción de que L1 sea un subconjunto de L2.
La opción b podemos decir que es verdadera, pero nos preguntamos si la opción d es también verdadera.
L1 reconoce cualquier cadena que contenga al menos una x, una y una z, por tanto reconoce todas las cadenas en el lenguaje L2 que han de tener obligatoriamente una x, una y y una z. Por tanto es cierto que L2 es subconjunto de L1.
Respondemos la opción d) porque es la que mejor describe la situación, aunque dado que la opción b) puede considerarse cierta y por tanto generar dudas, recomendamos escribir un comentario al respecto en el examen, en una hoja aparte.
-
PREGUNTA: La siguiente gramática con símbolo inicial S:
S -- > AB
A -- > Aa
A -- > a
B -- > Bb
B -- > b
a) Es una gramática regular.
b) Es una gramática independiente del contexto.
c) Ninguna de las anteriores.
RESPUESTA: la opción correcta es la b) (esta pregunta tiene “truco”, ver la explicación).
Trataremos de analizar qué cadenas genera la gramática. No hay derivaciones a la cadena vacía, por tanto la cadena vacía no forma parte del lenguaje. A puede derivar a una cadena con un mínimo de una a y un máximo de infinitas a´s. B puede derivar a una cadena con un mínimo de una b y un máximo de infinitas b´s. El símbolo inicial puede derivar a como mínimo ab, y a cualquier cadena con cualquier número de a´s antecediendo a cualquier número de b´s. Esto equivale a la expresión regular aa*bb*. ¿Siempre que una gramática representa un lenguaje regular es una gramática regular? Intuitivamente quizás respondamos que sí, pero lo cierto es que no, ahí está el truco o sutileza de esta pregunta.
Por ello nos tenemos que remitir a la definición de gramática regular. Una gramática es regular si cumple estos requisitos:
a) En el lado izquierdo de las reglas de producción solo aparece un símbolo
b) El lado derecho de las normas sólo puede contener dos cosas: un símbolo terminal (se acepta también la cadena vacía) ó un símbolo terminal seguido de un símbolo no terminal.
Por tanto no se aceptan reglas como A -- > Aa porque el símbolo no terminal no puede aparecer como primer símbolo en el lado derecho.
Tampoco se aceptan reglas como A -- > AB porque tiene dos símbolos no terminales seguidos en el lado derecho de la regla, por tanto la gramática propuesta no es regular.
Dado que los lenguajes regulares son un subconjunto de los lenguajes independientes del contexto y dado que las gramáticas independientes del contexto aceptan que en el lado derecho haya cualquier sucesión de símbolos (terminales o no terminales) concluimos que la gramática es una gramática independiente del contexto que genera un lenguaje regular.
Pregunta que parecía sencilla pero que ha resultado bastante más complicada de responder de lo que aparentaba.
-
PREGUNTA: Sea L1 el lenguaje generado por la gramática con símbolo inicial S. (Nota:La producción cb -- > bc indica que cada vez que aparezca la subcadena cb se transforma en la subcadena bc).
S -- > AB
A -- > aAc
A -- > ac
B -- > bB
B -- > b
cb -- > bc
y el lenguaje L2 = {anbncn : con n > 0}. Podemos afirmar que:
a) L1 = L2
b) L1 ⊂ L2
c) L2 ⊂ L1
d) L1 ≠ L2
RESPUESTA: la opción correcta es la c).
El lenguaje L2 sabemos que no es un lenguaje regular porque requiere tener capacidad para contar el número de veces que aparece cada símbolo (incluso podemos decir que no es un lenguaje independiente el contexto porque no nos va a bastar una pila para poder recordar cuántas a´s y cuántas b´s han aparecido y poder comparar esto con el número de c´s).
L2 acepta abc, aabbcc, aaabbbccc, etc.
Comencemos analizando qué lenguaje genera la gramática. La gramática no es regular (formalmente porque no cumple las condiciones), pero quizás genere un lenguaje regular, vamos a estudiarlo.
La rama de la A nos da lugar a cadenas tipo ancn, es decir, cadenas con el mismo número (balanceado) de a´s y c´s.
La rama de la B nos da lugar a cadenas tipo b+ ó bb*, es decir, una o más b´s.
La concatenación AB nos genera cadenas ancn bb*. La unión entre ambas ramas es cb que se transforma en bc según nos indican
Por tanto acb se transforma en abc
aaccb se transforma en aacbc; aaccbb se transforma en aacbcb
aaccbbbbbbb se transforma en aacbcbbbbbb
La gramática genera cadenas con el mismo número de c´s que de a´s, y con una o muchas b´s.
La opción a) la descartamos: no son lenguajes iguales.
La opción b: ¿es L1 un subconjunto de L2? No, aacbcbbbbbb pertenece a L1 pero no a L2, por tanto L1 no puede ser subconjunto de L2.
La opción c: ¿es L2 subconjunto de L1? Es decir, las cadenas de L2 ¿serán siempre cadenas de L1?. Sí porque tienen igual número de a´s que de c´s y una o muchas b´s. Por tanto responderemos la opción c).
La opción d) también puede considerarse válida puesto que son lenguajes distintos, aunque es “menos exacta” que la opción c). De cualquier manera, recomendamos comentar esta circunstancia en el examen.
-
PREGUNTA: Sea el lenguaje L = {xnym : n + m es un numero par}. ¿Cuál de las siguientes afirmaciones es verdadera?
a) El lenguaje L es un Lenguaje Regular.
b) El lenguaje L es un Lenguaje Independiente del Contexto no Regular.
RESPUESTA: La opción correcta es la a)
Si el lenguaje es regular podremos representarlo con una expresión regular, una gramática regular ó un autómata finito (determinista o no determinista).
En primer lugar tenemos que reflexionar sobre la definición del lenguaje. Nos dice m+n es un número par. Número par es todo número múltiplo de 2. ¿Es el cero un número par? Esto nos puede generar algo de duda, pero efectivamente el cero es un número par porque son pares todos los enteros multiplicados por 2, así son pares -8, -6, -4, -2, 0, 2, 4, 6, 8 … En este caso los números negativos no tienen sentido y el cero todavía no lo sabemos, pero sí sabemos que es par.
Veamos cadenas que genera el lenguaje:
a) Fijamos las x y vemos las posibles y´s teniendo en cuenta que son pares 0+0, 1+1, 1+3, 1+5… , 2+0, 2+2, 2+4, 2+6 …, 3+1, 3+3, 3+5, … , 4+0, 4+2, 4+4, 4+6…, : cadenas ε, xx, xyyy, xyyyyy, xx, xxyy, xxyyyy, xxyyyyyy, xxxy, xxxyyy, xxxyyyyy, etc.
b) Fijamos las y´s y vemos las posibles x`s: 0+0, 1+1, 2+2, 4+2, 6+2, 8+2 …, 1+3, 3+3, 5+3, 7+3, …, 2+4, 4+4, 6+4, 8+4, … , : cadenas ε, xx, xxyy, xxxxyy, xxxxxxyy, xyyy, xxxyyy, xxxxxyyy, xxxxxxxyyy, etc.
No descartamos que sea regular porque no vemos la necesidad de contar, sino de un autómata capaz de generar bucles de cierta manera.
El patrón observable es:
Si la x es impar, entonces el número de y´s admisible es 1, 3, 5, 7, 9 … , es decir, si x es impar y ha de ser impar
Si la x es par entonces el número de y´s admisible es 2, 4, 6, 8…, es decir, si x es par y ha de ser par
Si la y es impar, entonces el número de x´s admisible es 1, 3, 5, 7, 9 …
Si la y es par, entonces el número de x´s admisible es 2, 4, 6, 8
En resumen, si número de x´s es par número de y´s también ha de serlo, y si número de x´s es impar número de y´s también ha de serlo.
Vamos a tratar de generar una gramática regular que reconozca el lenguaje:
S -- > ε | xAyB
A -- > ε | xxA
B -- > ε | yyB
Genera: ε y cadenas con x´s impares e e impares, lo que da lugar a que la suma de x´s e y´s sea par.
Pero ojo: la gramática anterior no es regular desde el punto de vista formal.
Ahora tratemos de ampliar a la posibilidad de x´s pares e y´s pares.
S -- > ε | xAyB | AB
A -- > ε | xxA
B -- > ε | yyB
Esta gramática parece generar el lenguaje. Ahora nos preguntamos ¿es regular el lenguaje?
Sabemos transformar gramáticas regulares en autómatas finitos, pero como esta gramática no es regular no podemos aplicar el “método conocido” y vamos a tratar de hacerlo intuitivamente.
(http://i.imgur.com/wmPNaNh.png)
Nota: formalmente deberíamos tener estados intermedios en cadenas como xx ó yy, pero como lo único que nos interesaba era ver si era un lenguaje regular hemos abreviado no representando las transiciones carácter a carácter.
Este autómata finito determinista representa el lenguaje, que por tanto consideramos que es regular.
Ahora vamos a intentar expresar el lenguaje como expresión regular:
L = (ε | x(xx)*y(yy*) | (xx)*(yy)* )
Esta expresión parece generar el lenguaje, por tanto todo indica que es regular.
¿Es necesario todo este desarrollo para responder esta pregunta? No, basta con de alguna manera llegar a la conclusión correcta de que el lenguaje es regular. Si a ti se te ha ocurrido directamente la expresión regular que representa el lenguaje, por ejemplo, y has tardado un minuto, genial. Nosotros hemos tardado bastante más tiempo… ???
-
PREGUNTA: Sea el lenguaje L = {xnymzn : con n y m > 0, y m = n/2}. ¿Cuál es la máquina más simple que puede reconocer este lenguaje?
a) Un autómata finito.
b) Un autómata a pila determinista.
c) Un autómata a pila no determinista.
d) Una máquina de Turing.
RESPUESTA: la opción correcta es la d).
El enunciado no deja claro qué ocurre si n no es par, en ese caso m no sería un valor entero lo cual no tendría sentido, por lo que vamos a suponer que se exige que n sea par (0, 2, 4, 6, 8, …). Si n es 0 m es 0, lo que significa que se admite la cadena vacía.
Cadenas admitidas serían: ε, xxyzz, xxxxyyzzzz, xxxxxxyyyxxxxxx, etc.
Para verificar que el número de y´s es la mitad que el número de x necesitamos contar, con lo cual podemos descartar que se trate de un lenguaje regular y descartamos la opción a.
Con una pila podríamos apilar un símbolo por cada dos x´s leídas, y posteriormente desapilar un símbolo por cada y leída, pero después no tenemos capacidad para recordar la cantidad de x´s aparecidas, cosa que sí podemos hacer con una máquina de Turing.
Nota: hay preguntas muy similares que tienen una respuesta distinta, así que no recomendamos “memorizar” sino “tratar de razonar”.
-
PREGUNTA: Dado el lenguaje L definido por la gramática:
S -- > xS
S -- > Sy
S -- > xy
y la siguiente máquina de Turing que reconoce el lenguaje L:
(http://i.imgur.com/juf5npw.jpg)
Podemos asegurar que el lenguaje es recursivamente enumerable no regular
a) Verdadero.
b) Falso.
RESPUESTA: la opción correcta es la b).
Analicemos qué cadenas pertenecen al lenguaje: S -- > xS permite generar cadenas que empiezan por una x y tienen cualquier número de x´s, terminando en una xy debido a la producción que permite finalizar S -- > xy. Por ejemplo xxy, xxxy, xxxxy, etc. Expresado como expresión regular x*(xy)
S -- > Sy permite generar cadenas que empiezan con una xy, y tienen a continuación cualquier número de y´s. Expresado como expresión regular (xy)y*
Si comenzamos con S -- > xS y sustituimos S por Sy, xSy, resulta que podemos insertar tantas x´s como queramos y tantas y´s como queramos, siempre las x´s primero y las y´s después. Expresado como expresión regular x x* y* y
Las expresiones x*(xy) y (xy)y* son subconjuntos de la expresión que representa el lenguaje que es x x* y* y, que además podemos ver representada en la máquina de turing, que puede transformarse fácilmente en un autómata finito determinista.
Si lo podemos expresar como expresión regular o con un autómata finito, es que el lenguaje es regular. Por tanto respondemos la opción b), es falso que sea no regular.
-
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 todas las preguntas a la vez sin consultar ningún tipo de documentación, y luego comprobar cómo nos hubiera ido en ese caso supuesto "real" y qué nota habríamos sacado. Para quien quiera intentarlo, dejo el examen con enunciados completos en el archivo adjunto a este post (archivo jun12_1a_sem_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...
-
PREGUNTA: ¿Un autómata finito puede reconocer una palabra con solo llegar al estado de aceptación?
a) Si.
b) No.
RESPUESTA: la opción correcta es la b).
Un autómata finito reconoce una palabra cuando se cumplen dos condiciones:
a) Haber llegado a un estado de aceptación
b) Haber consumido todos los caracteres de la palabra de entrada
Llegar a un estado de aceptación sin haber consumido todos los caracteres de entrada no implica el reconocimiento de la palabra.
Pregunta que parece simple pero no lo es tanto como parece.
-
PREGUNTA: ¿Un autómata finito puede reconocer una palabra sin llegar al estado de aceptación?
a) Si.
b) No.
RESPUESTA: la opción correcta es la b).
Un autómata finito reconoce una palabra cuando se cumplen dos condiciones:
a) Haber llegado a un estado de aceptación.
b) Haber consumido todos los caracteres de la palabra de entrada.
Sin llegar a aceptación no puede haber reconocimiento de una palabra.
-
PREGUNTA: Dada la expresión regular ((a + b + acb + ba)* + (a* + bc*))* c (( ac* + b*) + (a + bc)*)* . Podemos asegurar que el lenguaje que define es:
a) Un lenguaje regular.
b) Un lenguaje independiente del contexto determinista, no regular.
c) Un lenguaje independiente del contexto no determinista, no regular.
d) Un lenguaje recursivamente enunmerable, no independiente del contexto.
RESPUESTA: la opción correcta es la a).
Si el lenguaje está definido por una expresión regular bien formada, se trata de un lenguaje regular. Además será independiente del contexto y recursivamente enumerable, ya que estos son superconjuntos de los lenguajes regulares.
-
PREGUNTA: Sea la expresión regular ((abc)* + (acb)* + (bac)* + (bca)* + (cab)* + (cba)*)*
a) Todas las cadenas del lenguaje tienen un número impar de letras.
b) El lenguaje está formado por todas las posibles cadenas que tengan el mismo número de a's, b's y c's.
c) El lenguaje está formado por cadenas que tengan el mismo número de a's, b's y c's que empiecen por la subcadena "abc" y terminen con la subcadena "cba".
d) Ninguna de las anteriores.
RESPUESTA: La opción correcta es la d)
El lenguaje definido por la expresión regular admite la cadena vacía, por tanto no es cierto que todas las cadenas del lenguaje tengan un número impar de letras y descartamos la opción a).
El lenguaje no admite aabbcc por lo que es falso que esté formado por todas las posibles cadenas que tengan el mismo número de as, bs y cs. Descartamos entonces la opción b).
El signo + equivale a opcionalidad (equivale al OR lógico) por lo que las cadenas pueden empezar con abc, acb, bac, bca, cab ó cba y terminar con cualquiera de ellas también por lo que descartamos la opción c).
Por tanto respondemos la opción d), ninguna de las anteriores.
-
PREGUNTA: Dada la siguiente máquina podemos afirmar:
(http://i.imgur.com/yfaa5MK.jpg)
a) Es una máquina de Turing mal definida ya que no se indica el movimiento a realizar.
b) Es un autómata finito determinista.
c) Es un autómata a pila determinista.
d) Es un autómata a pila no determinista.
RESPUESTA: la opción correcta es la d).
La máquina representada es un autómata a pila donde la notación x, y; h indica que se lee el símbolo x de la cadena de entrada estando el símbolo y en la cima de pila, se pone el símbolo h en cima de pila y se realiza la transición que corresponda.
Se trata de un autómata a pila no determinista porque para un mismo símbolo de entrada y símbolo en cima de pila define dos transiciones distintas posibles (por ejemplo se permite una transición que sin leer ningún símbolo de entrada y teniendo S en la cima de pila ponga bien A en la pila o bien B).
Este autómata tiene la forma usual de autómata construido a partir de una gramática (aunque aquí no nos preguntan nada relacionado con esto).
-
PREGUNTA: Dado el lenguaje L = {xnyn : n > 0}. Podemos afirmar que:
a) Las dos máquinas de Turing de las opciones c y d reconocen el lenguaje L.
b) Ninguna de las máquinas de Turing de las opciones c ó d reconoce el lenguaje L.
(http://i.imgur.com/bqkRJeg.jpg)
RESPUESTA: respondemos la opción a), pero ver comentarios.
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.
Miramos a la máquina de la opción c) y nos preguntamos si acepta xxyy
q0xxyy ├ aq1xyy├ axq1yy ├ axyq1y ├ axyyq1 ├ si suponemos que λ es blanco pasamos a q2 moviéndonos a izquierda ├ axyq2y ├ axq3y ├ aq3xy ├ q3axy ├ q0λxy ├ FλSxy y aceptación. Sí acepta.
¿Acepta xy?
q0xy ├ aq1y ├ ayq1λ ├ aq2y ├ q3a ├ q0 λx ├ FλSx y aceptación. Sí acepta.
Esta máquina parece reconocer cualquier cadena formada por al menos una x y una y, por tanto reconocería el lenguaje L (y más cadenas).
Miramos a la máquina de la opción d). Si reconoce el mismo lenguaje L debería reconocer xxyy.
qoxxyy ├ λq0xyy ├ λλqoyy ├ λλλq1y ├ λλλλq1B ├ si suponemos que λ representa B la máquina pasa al estado de aceptación F.
¿Reconoce xyy?
q0xyy ├ q0yy ├ q1y ├ q1λ ├ λF λ y aceptación. Esta cadena no pertenece a L.
Sí la reconoce, esta máquina parece reconocer cualquier cadena del tipo xx*yy*, es decir, cualquier cadena con al menos una x y al menos una y. El lenguaje L es un subconjunto de este lenguaje, por tanto la máquina de la opción d) reconoce el lenguaje L.
Todo apunta a que ambas máquinas reconocen un lenguaje (más amplio que L) que incluye al lenguaje L, por lo que respondemos la opción a). Podríamos pensar que estas máquinas no reconocen exactamente el lenguaje L, pero la pregunta es simplemente si reconocen L, no si reconocen exactamente sólo el lenguaje L (esto es una interpretación que estamos haciendo nosotros).
Pregunta que nos ha resultado difícil de responder, en parte porque el enunciado puede considerarse un tanto ambiguo y en parte porque las máquinas de Turing un poco complejas pueden resultar difíciles de interpretar. Recomendamos comentar este tipo de preguntas en el examen para indicar el razonamiento y consideraciones que se han tomado para responder.
-
PREGUNTA: Dado el siguiente autómata podemos afirmar:
(http://i.imgur.com/pweE3zT.jpg)
a) El conjunto de letras que forman las palabras reconocidas por el autómata es {x}.
b) El conjunto de letras que forman las palabras reconocidas por el autómata es {x, y}.
c) El conjunto de letras que forman las palabras reconocidas por el autómata es {x, y, c}.
d) El conjunto de letras que forman las palabras reconocidas por el autómata es {x, y, c, d}.
RESPUESTA: La opción correcta es la b).
Se trata de un autómata a pila que en primer lugar pone el símbolo # como fondo de pila y luego introduce el símbolo S en la pila.
Este autómata parece representar una gramática que vamos a escribir a partir de las reglas del autómata:
S -- > A
S -- > B
A -- > xAy
B -- > xxBy
A -- > xy
B -- > xxy
B -- > cCd
A -- > cCd
C -- > cCd
Para que un no terminal pueda intervenir en el lenguaje son necesarias dos condiciones:
a) Que sea alcanzable
b) Que permita derivar en algún momento a símbolos terminales o a la cadena vacía λ
Analicemos lo que ocurre con cada no terminal:
S: permite derivar a A y B
A: tiene una regla recursiva pero también una regla finalista que deriva a los terminales xy
B: tiene una regla recursiva xxBy, y otra regla que deriva a cCd. También una regla finalista que permite derivar a los terminales xxy
C: sólo deriva a una regla recursiva donde interviene el mismo símbolo C. Por tanto este símbolo no puede utilizarse para generar palabras del lenguaje, porque si se introdujera alguna producción donde intervenga C luego no habría forma de eliminar C derivando a símbolos terminales.
Debido a lo anterior, únicamente podemos construir palabras utilizando A y B, y estas palabras únicamente pueden incluir los símbolos {x, y}. Por tanto respondemos la opción b).
Si no analizamos la gramática con cuidado podemos pensar que la solución es {x, y , c, d} pero no sólo hay que considerar si un no terminal es alcanzable, sino también si permite finalizar las recursiones para construir cadenas válidas. ¡Hay que fijarse!
-
PREGUNTA: ¿Cuál de las siguientes máquinas tienen mayor capacidad de representación?:
a) Las máquinas de Turing no deterministas.
b) Las máquinas de Turing deterministas.
c) Las máquinas de Turing de múltiples cintas.
d) Todas las anteriores máquinas tienen la misma capacidad de representación.
RESPUESTA: la opción correcta es la d).
Pregunta sencilla de responder si se ha estudiado lo suficiente. Recordar: todas las máquinas de Turing (de un tipo u otro) tienen la misma capacidad de representación (aunque el coste de computación puede diferir, pero la capacidad de reconocimiento es la misma).
-
PREGUNTA: ¿Una máquina de Turing puede reconocer una cadena de un lenguaje decidible con solo llegar al estado de parada?
a) Si.
b) No.
RESPUESTA: la opción correcta es la b).
En primer lugar aclaremos que decidible significa que existe un algoritmo capaz de resolver el problema con coste temporal polinomial, llegando a parada bien porque la cadena de entrada se rechace como no perteneciente al lenguaje o bien porque la cadena se acepte como sí perteneciente al lenguaje. Por tanto para que una máquina de Turing reconozca una cadena de un lenguaje decidible hacen falta dos cosas:
a) Llegar a parada (solución del problema)
b) Que la parada se produzca en un estado de aceptación (esto indica que se ha reconocido la cadena).
-
PREGUNTA: ¿Cuál de los siguientes autómatas tienen mayor capacidad de representación?:
a) Los autómatas finitos no deterministas.
b) Los autómatas finitos deterministas.
c) Todos los autómatas anteriores tienen la misma capacidad de representación.
RESPUESTA: la opción correcta es la c).
Los autómatas finitos no deterministas pueden transformarse en autómatas finitos deterministas siguiendo una serie de pasos, luego ambos tienen igual capacidad de representación o reconocimiento de lenguajes.
-
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 sept12_orig_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...
-
PREGUNTA: Sea L1 el lenguaje definido por la gramática
S -- > xxxxxAyy, A -- > xxxxxAyy, S -- > xxxxxxxBy, B -- > xxxxxxxBy, A -- > λ, B -- > λ,
con símbolo inicial de la gramática S. Sea L2 el lenguaje formado por las cadenas del lenguaje L1 con una cardinalidad máxima de 35 letras. Podemos afirmar:
a) Que el lenguaje L2 es un lenguaje regular por estar acotada la cardinalidad de las cadenas, y que se puede reconocer con un autómata finito determinista de 7 estados que es mayor que el número máximo de producciones utilizadas en la generación de las palabras.
b) Como la cardinalidad de las palabras del lenguaje L2 está acotada a un valor que asegura que sólo se pueda utilizar o la producción A -- > λ, o la producción B -- > λ y no las dos para la generación de todas las palabras del lenguaje, entonces podemos asegurar que se puede reconocer el lenguaje L2 con un autómata a pila determinista.
c) Como el lenguaje L2 es regular y puede ser reconocido por un autómata finito, el lenguaje L1 tiene que ser regular.
d) Como el lenguaje L1 es reconocido por un autómata a pila no determinista, sólo un autómata a pila no determinista puede reconocer el lenguaje L2
RESPUESTA: La opción correcta es la b).
El lenguaje L2 está formado por un número finito de cadenas, por tanto puede ser representado por un autómata finito y por tanto es un lenguaje regular.
La gramática de L1 podemos verla como formada por dos ramas:
S -- > xxxxxAyy, A -- > xxxxxAyy, S -- > xxxxxxxBy, B -- > xxxxxxxBy, A -- > λ, B -- > λ
La rama A nos lleva a cadenas con un número de x´s múltiplo de 5, y un número de y´s múltiplo de 2 de la forma n*(x5y2) donde n>0 . Quedan dentro del lenguaje cinco x´s seguidas de dos y´s, diez x´s seguidas de 4 y´s, quince x´s seguidas de seis y´s, etc.
La rama B nos lleva a cadenas con un número de x´s múltiplo de 7 y un número de y´s la séptima parte del número de x´s, de la forma n*(x7y) donde n>0. Quedan dentro del lenguaje siete x´s seguidas de una y, catorce x´s seguidas de dos y´s, veintiuna x´s seguidas de tres y´s, etc.
¿L1 podemos representarlo con una expresión regular? No, podemos apreciar que necesitamos contar: por cada 5 x´s contadas añadir 2 y´s al final por ejemplo requiere que contemos las x´s. Si necesitamos contar no es un lenguaje regular y no es representable con un autómata finito.
¿L1 podemos representarlo con un autómata a pila? Por cada cinco x´s podemos añadir un símbolo a la pila, y luego por cada 2 y´s desapilar el símbolo añadido previamente, por tanto podemos representarlo con un autómata a pila determinista y podemos decir que es un lenguaje independiente del contexto.
Analizamos las opciones:
Opción a) Si tenemos cadenas de hasta 35 letras que tenemos que reconocer una a una vamos a necesitar muchos estados, por lo menos 35 pero como hay muchas variantes podríamos estar hablando de bastantes decenas más de estados necesarios. Tener en cuenta que no podemos crear un bucle en el autómata porque entonces no podríamos verificar que la palabra más grande tenga 35 letras. Por tanto esta opción es falsa.
Opción b) Verdadera
Opción c) Falsa, L1 es un lenguaje y L2 otro distinto. Que L2 sea un subconjunto de L1 no significa necesariamente que los lenguajes sean del mismo tipo (de hecho no lo son).
Opción d) Es falsa, L2 puede ser reconocida por un autómata finito.
-
PREGUNTA: Dado el lenguaje L = {xn : n = ∞}, esto es, el lenguaje que tiene una única cadena de cardinalidad infinita. Podemos asegurar que se puede reconocer con un autómata finito no determinista.
a) Si.
b) No.
RESPUESTA: la opción correcta es la b).
Supongamos que la cadena fuera “blas”. Con un autómata finito determinista podríamos partir de un estado inicial q0, pasar a un estado q1 al reconocer una b, pasar a q2 al reconocer una l, pasar a q3 al reconocer una a, y pasar a un estado de aceptación q4 al reconocer una s. Desde q4 volveríamos a q1 en caso de reconocer una b. Con este autómata podemos reconocer la expresión regular blas(blas)* ó escrito de otra manera, blas+ (una repetición o más de blas). Esto nos permite reconocer cadenas finitas que tengan cualquier número de veces repetida la cadena blas.
Pero la pregunta es relativa a si podemos reconocer una cadena donde blas se repite infinitas veces. Esto no podemos hacerlo con ningún tipo de máquina, ya que una cadena infinita significa que nunca terminaríamos el proceso de reconocimiento.
El lenguaje que reconoce un autómata puede ser infinito, pero las cadenas que reconoce siempre han de ser finitas, de otra forma no hay manera de terminar el proceso de reconocimiento. Por tanto respondemos la opción b). Motivo: una cadena infinita no puede ser reconocida por una máquina.
-
PREGUNTA: Suponga que extendemos los operadores utilizados para expresar las expresiones regulares con el operador " ' ", el cual significa que aquello a lo que eleve se puede repetir una o más veces. Por ejemplo:
• a' = a, aa, aaa, aaaa, ...
• (ab)’ = ab, abab, ababab, abababab, ...
• (a + b)' = a, b, aa, bb, ab, ba, aaa, aab, aba, baa, abb, bab, bba, bbb ...
Con este operador, ¿se amplia la capacidad de expresión de las expresiones regulares?, ¿se puede definir la expresión regular de un lenguaje que no se podía con anterioridad?
a) Si
b) No
RESPUESTA: la opción correcta es la b).
La repetición de un símbolo a una o más veces se puede representar en lenguajes regulares de dos maneras: como a+ o bien como aa*.
Por tanto todo lo que se puede hacer con este operador ya se podía hacer con los operadores existentes para las expresiones regulares. No se amplía la capacidad de expresión de las expresiones regulares. No se puede definir ninguna expresión que no se pudiera definir con anterioridad. Por tanto la respuesta es la b), este operador no aporta nada nuevo.
-
PREGUNTA: Dado el lenguaje formado por todas las posibles cadenas que tengan el mismo número de a's, de b's y de c's. La expresión regular que mejor define el lenguaje sería:
a) Ninguna de las siguientes
b) ( ( abc)* + (acb)* + (bac)* + (bca)* + (cab)* + (cba)*)*
c) (a*b*c*)*
d) (anbncn) , con n > 0.
RESPUESTA: la opción correcta es la a).
Las permutaciones o posibles combinaciones de a, b y c son:
Fijamos la a y cambiamos las otras letras: abc, acb
Fijamos la b y cambiamos las otras letras: bac, bca
Fijamos la c y cambiamos las otras letras: cab, cba
La opción b permite introducir cualquiera de estas cadenas un número indefinido de veces, lo que nos permite construir cadenas que siempre tendrán el mismo número de a´s, b´s y c´s. Pero podemos poner dos objeciones por las que no representa bien el lenguaje:
1.Se admite la cadena vacía, que no pertenece al lenguaje de cadenas con el mismo número de a´s, b´s y c´s si consideramos que debe aparecer al menos una a, una b y una c.
2. No representa cadenas del lenguaje como aaabbbccc
La opción c) no garantiza que las cadenas tengan mismo número de a´s, b´s y c´s. Define un lenguaje que contiene al propuesto pero que es mucho más amplio.
La opción d) no es una expresión regular.
Respondemos por tanto: “a) Ninguna de las siguientes”
Nota: recomendamos comentar en el examen que la opción b) es la que más se asemeja al lenguaje propuesto, pero que no lo define correctamente.
-
Dado el lenguaje L = {xnynzn : 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.
-
PREGUNTA: La máquina de Turing representada a continuación, no controla el orden de aparición de los elementos del alfabeto Σ = {x, y}
(http://i.imgur.com/2gBcU1y.jpg)
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 :).
-
PREGUNTA: Dado el siguiente autómata
(http://i.imgur.com/XVUTbBl.jpg)
podemos afirmar:
a) Reconoce el lenguaje L definido por la expresión regular x*y*
b) Reconoce el lenguaje L = {xnyn : n > 0}
c) Reconoce el lenguaje L = {xny2n : 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 xnyn
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 x2nyn
El lenguaje admitido por el autómata podríamos definirlo como L = { xnyn U x2nyn 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 = {xnyn : 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 = {xny2n : 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).
-
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.
-
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.
-
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 :)
-
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...
-
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…
(http://jamillan.com/librosybitios/files/2010/09/parte-300x221.jpg)
-
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).
-
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.
-
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).
-
PREGUNTA: Considere el siguiente autómata a pila.
(http://i.imgur.com/Ukkt3uu.jpg)
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 {xn+2 yn | n >= 0}
b) El autómata es no determinista y acepta el lenguaje {xn+2 yn | 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).
-
PREGUNTA: Indicar cuál es el tipo de autómata más sencillo (menor capacidad de reconocimiento) capaz de reconocer el lenguaje {xnymzn | 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).
-
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.
-
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.
-
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:
(http://i.imgur.com/l0HeEYf.png)
Hemos representado el lenguaje con un autómata finito, por tanto es un lenguaje regular y respondemos la opción a).
-
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.
-
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...
-
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.
-
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.
-
PREGUNTA: Sea L el lenguaje que reconoce el siguiente autómata finito
(http://i.imgur.com/HrgbJKh.jpg)
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).
-
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.
-
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.
-
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:
(http://i.imgur.com/5q2gbxV.jpg)
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 {0n1n: n >= 0}
b) El lenguaje que reconoce es {0n1n: n >= 1}
c) El lenguaje que reconoce es {0m1n: 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) {0n1n: 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:
q001 ├ Xq11 ├ q2XY ├ Xq0Y ├ XYq3B├ XYBq4 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:
q00101 ├ Xq1101 ├ q2XY01 ├ Xq0Y01 ├ XYq301 ├ … en q3 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:
q00011 ├ Xq1011 ├ X0 q111 ├ Xq20 Y1 ├ q2X0 Y1 ├ X q00Y1 ├ XX q1Y1 ├ XX q1Y1 ├ XX Y q11 ├ XXq2YY ├ X q2XYY ├ XXq0YY ├ XXY q3Y ├ XXYY q3B ├ XXYYBq4 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:
(http://i.imgur.com/Pn8315B.png)
-
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:
(http://i.imgur.com/06INxBL.jpg)
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.
-
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).
-
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.)
(http://i.imgur.com/z1PM5T7.jpg)
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 {xnyn: 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 {xnyn: 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).
-
PREGUNTA: El lenguaje L = {0i1j2k | 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.
-
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...
-
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.
(http://i.imgur.com/yZDcTPx.jpg)
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).
-
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.
-
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).
-
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
-
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):
(http://i.imgur.com/xn3cTA0.jpg)
¿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”.
-
PREGUNTA: Indicar para qué valores de las etiquetas Etiqueta-1 y Etiqueta-2, el autómata de la figura representa el lenguaje {xn+1 yn : n >=0}. Se supone que inicialmente la pila se encuentra vacía y que el símbolo inicial de la pila es Zo.
(http://i.imgur.com/ZMy3yIO.jpg)
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.
-
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):
(http://i.imgur.com/oWBjaJ8.jpg)
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.
-
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).
-
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.
-
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.
-
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...
-
PREGUNTA: Considere la gramática de símbolos terminales {(, ), ; , 1,2, 3}, símbolos no terminales {S, A, E} y producciones:
S --> (A)
A --> A;E | E
E --> 1 | 2 | 3 | S
La gramática genera listas de elementos que son números o a su vez listas separadas por el símbolo ";". Indicar cuál de las siguientes afirmaciones es verdadera:
a) El lenguaje es regular
b) El lenguaje es independiente del contexto no regular
c) No existe una gramática equivalente en Forma Normal de Chomsky
RESPUESTA: la opción correcta es la b)
Estudiamos la gramática propuesta y tratamos de ver qué cadenas genera:
Si en S --> (A) sustituimos A podemos tener:
(A;E) y a su vez ((A);E) y a su vez (((A));E) … que nos lleva a una salida de tipo (((1));2)
Por tanto podemos generar (numero;numero), ((numero);numero), (((numero));numero) … etc.
Tenemos que fijarnos en una cosa: los paréntesis están balanceados, es decir, por cada paréntesis de apertura tiene que haber un paréntesis de cierre.
Podemos intentar describir una expresión regular, pero nos vamos a encontrar con que no nos es posible hacer que los paréntesis se balanceen. Por ejemplo (usamos corchetes para indicar agrupación y diferenciarlo del carácter paréntesis):
[(numero;numero)] | [ ( [(numero)]+;numero) ]
Nos llevaría a cadenas como ((3)(1);2) donde se generan paréntesis balanceados pero insertando siempre un número con paréntesis detrás de otro.
Para balancear paréntesis como hace la gramática necesitamos contar, y la máquina más básica con capacidad para contar es un autómata a pila, ya que los autómatas finitos (lenguajes regulares) no tienen capacidad para contar. Por tanto la opción a) es falsa, no es un lenguaje regular.
Con un autómata a pila podemos generar este lenguaje, por tanto es un lenguaje independiente del contexto no regular. Provisionalmente vamos a responder la b), pero antes examinemos la opción c).
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 los paréntesis de apertura y cierre. Por tanto sí existe una gramática en FNC y podemos decir que la opción c) es falsa.
Respondemos por tanto la opción b)
-
PREGUNTA: Dada la siguiente expresión regular: (((a + b) c* (a + b)) + (( ac + ab) *))* y el siguiente autómata finito:
(http://i.imgur.com/1z0BEHA.jpg)
Indicar qué valores deben tener Etiqueta-1 y Etiqueta-2 para que el autómata acepte el mismo lenguaje que la expresión regular:
a) Etiqueta-1=a, b Etiqueta-2=a
b) Etiqueta-1=c Etiqueta-2=a
c) Etiqueta-1=a Etiqueta-2=a, b
d) Ninguna de las anteriores combinaciones es válida
RESPUESTA: la opción correcta es la c), aunque ver comentarios.
Nos dice que el autómata debe aceptar el mismo lenguaje, pero esto no deja claro si debe ser exactamente el mismo lenguaje, o podría reconocer un lenguaje más amplio que englobe el lenguaje de la expresión regular. Si se considerara oportuno, se podría incluir un comentario en el examen para indicar qué interpretación hemos hecho.
Nos fijamos primero en si la expresión regular admite ε, ya que el autómata admite ε por ser el estado inicial un estado de aceptación. Dado que el conjunto de la expresión regular está afectada por un asterisco de Kleene, efectivamente admite ε.
La expresión regular y el autómata no son fáciles de analizar con un simple vistazo, requiere un tiempo y posiblemente se pueda hacer de distintas maneras.
( ac + ab) * está contenido en la rama de abajo del autómata.
((a + b) c* (a + b)) está contenido en la rama de arriba del autómata.
Para ligar la rama de arriba con la de abajo necesitamos que etiqueta-1 sea a ya que la rama de abajo sólo admite comienzos por la letra a, mientras que para ligar la de abajo con la de arriba necesitamos que etiqueta-2 sea a,b ya que la rama de arriba admite inicios tanto con a como con b.
Otra forma de razonarlo: plantear cadenas que admite la expresión regular y ver qué valores de etiquetas se requerirían en el autómata:
La ER admite acccaac: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.
La ER admite acccaab: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.
La ER admite abacccb: no intervienen las etiquetas
La ER admite acbac: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 en principio nos da igual.
La ER admite acbacbb: para que el autómata admita esta cadena Etiqueta-1=a, la etiqueta 2 ha de ser Etiqueta-2=b.
Vemos que la Etiqueta-1 ha de ser a. La Etiqueta-2 tendría que ser b. Respondemos entonces la opción c). Esta pregunta tiene su complejidad, no permite de forma clara tener seguridad de que la conclusión a la que llegamos sea con certeza la correcta.
-
PREGUNTA: La estrella de Kleene o clausura de un lenguaje independiente de contexto, ¿es siempre un lenguaje independiente de contexto?
a) Sí, siempre
b) No, nunca
c) Depende de los casos
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 y 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, la estrella de Kleene aplicada a un 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.
-
PREGUNTA: Indicar cuál de los siguientes lenguajes NO es regular:
a) L = {w ∈ {a, b}* | abab es subcadena de w}
b) L = {w ∈ {a, b}* | w ∉ {anbn} : n > 0}
c) El lenguaje consistente en las cadenas de caracteres tales que dos a's están separadas por 4i símbolos para algún entero i >= 0
RESPUESTA: la opción correcta es la b).
Recordar que lenguaje no regular es el que:
a) No cumple el lema de bombeo para lenguajes regulares
b) No puede ser representado con un autómata finito
c) Necesita una pila o cinta para “recordar”
El lenguaje de la opción a) podemos expresarlo como (a+b)*abab(a+b)* y resulta un lenguaje regular, o al menos lo parece.
El lenguaje de la opción b) requiere contar el número de a´s y comprobar que no es igual al número de b´s. Necesitamos la capacidad de contar, y no podemos basarnos en un número finito de posibilidades porque el número de a´s y b´s es ilimitado. Por tanto no se puede representar con un autómata finito y no es un lenguaje regular.
El lenguaje de la opción c) podría representarse con un autómata que admite cualquier carácter en su estado inicial q0, y cuando recibe una a se mueve a un estado q1, un carácter distinto de a lleva a q2, otro carácter distinto de a mueve a q3 y con el siguiente carácter distinto de a mueve a q4. Para salir de q4 si el carácter recibido es distinto de a se vuelve a q0, y en caso de ser a se vuelve a q1
Serían estados de aceptación q0 (ya que se admite i=0)
No serían estados de aceptación q1, q2, q3, q4
Si es representable con un autómata finito el lenguaje es regular. La definición de este lenguaje no es del todo clara, pero parece que se adaptaría a la definición de lenguaje regular.
Respondemos por tanto la opción b).
-
PREGUNTA: Sea L el lenguaje generado por la siguiente gramática:
S -- > xxSyy | xy
Indicar cuál de las siguientes afirmaciones es verdadera:
a) L está formado por cualquier cadena que tenga el mismo número de x's que de y's.
b) L está formado por cualquier cadena que tenga el mismo número de x's que de y's, y que además tenga un número par de símbolos.
c) L está formado por cualquier cadena que tenga el mismo número par de x's y de y's.
d) Ninguna de las anteriores afirmaciones es verdadera.
RESPUESTA: la opción correcta es la d).
La opción a) es falsa puesto que la gramática impone que las x´s han de venir antes que las y´s, por tanto cualquier cadena con el mismo número de x´s que de y´s no será válida. Por ejemplo yyxx no es válida.
La opción b) es falsa por el mismo motivo.
La opción c) es falsa por el mismo motivo, además el número de x´s o de y´s puede no ser par (aunque la cadena en su conjunto sí tenga un número de símbolos par.
Respondemos por tanto la opción d).
-
PREGUNTA: Indicar cuál es el autómata más sencillo (con menor capacidad de reconocimiento) que funcione de la siguiente manera. Dada cualquier cadena de x e y, substituya todas las x's por z's y devuelva una cadena con todas las y's al principio y las z's a continuación
a) Un autómata finito.
b) Un autómata a pila determinista.
c) Un autómata a pila no determinista.
d) Una máquina de Turing.
RESPUESTA: la opción correcta es la d).
Dado que el autómata ha de devolver algo, necesitamos un autómata que pueda devolver un resultado. Esto tendría que hacerse a través de una pila donde quede reflejado el resultado, o a través de una cinta de una máquina de Turing. Por tanto descartamos la opción a) Un autómata finito ya que estos autómatas no pueden devolver (al menos de forma explícita) un resultado.
Pensemos en un ejemplo. Si recibimos xyxyxxxyyy el autómata primero ha de leer todos los caracteres para sustituir las x´s por z´s, en este ejemplo zyzyzzzyyy. Después tiene que devolver una cadena con todas las y´s al principio y las z´s al final, en este ejemplo yyyyyzzzzz
Un autómata a pila puede introducir en la pila una z por cada x leída y una y por cada y leída. Una vez leída la cadena un autómata a pila no puede volver atrás, aunque sí podría realizar transiciones espontáneas sin consumir caracteres (leyendo la cadena vacía y modificando la pila). Pero pudiendo explorar sólo la cima de pila, no tendríamos forma de realizar una ordenación como la requerida (donde necesitaríamos poder enviar las y´s al final de la estructura de datos, pero una pila no nos permite hacer esto). Descartamos las opciones b) y c) por tanto.
Una máquina de Turing tiene la misma capacidad de computación que un computador y puede realizar esta tarea sin problema. Respondemos por tanto la opción d).
-
PREGUNTA: ¿Qué podemos afirmar del siguiente autómata?
(http://i.imgur.com/P5lDam1.jpg)
a) Es un autómata no determinista que reconoce cadenas de x e y de tamaño mayor o igual a dos.
b) Está mal definido, ya que tiene dos estados de aceptación.
c) No tiene en cuenta la cantidad de símbolos z que se leen de la cadena de entrada.
d) Ninguna de las anteriores.
RESPUESTA: la opción correcta es la c).
¿Es un autómata determinista o no determinista? Es un autómata determinista, puesto que no hay dos transiciones definidas para un mismo carácter de entrada. Por ello descartamos la opción a).
¿Está mal definido por tener dos estados de aceptación? No tiene por qué, un autómata puede tener ninguno, uno o más de un estados de aceptación.
¿Tiene en cuenta la cantidad de símbolos z que se leen de la cadena de entrada? El autómata puede llegar a aceptación con cero, uno o más de un símbolo z en la cadena de entrada. Por tanto la respuesta a la pregunta anterior es no.
La pregunta resulta un tanto confusa porque nos podemos preguntar si el autómata acepta la cadena zx y la respuesta es no, y esto pareciera dar a entender que sí se tiene en cuenta entonces la cantidad de símbolos z´s. Pero el autómata rechaza zx no porque tenga en cuenta el número de z´s en la cadena de entrada, sino porque la cadena no está contemplada como cadena del lenguaje definido.
-
PREGUNTA: Indique cuál de las siguientes afirmaciones es verdadera:
a) Dado un alfabeto Σ, para cualquier lenguaje construido sobre Σ existe una máquina de Turing que lo acepta
b) Dado un alfabeto Σ, cualquier lenguaje construido sobre Σ es recursivamente enumerable
c) Dado un alfabeto Σ, existen lenguajes construidos sobre Σ que no son recursivamente enumerable s y para los cuales no se puede construir una máquina de Turing que los acepte.
RESPUESTA: la opción correcta es la c).
Las máquinas de Turing son las máquinas abstractas con mayor capacidad de reconocimiento de un lenguaje (y capacidades computacionales análogas a las de un computador) pero esto no significa que tengan capacidad para reconocer todos los lenguajes. De hecho, los lenguajes no reconocidos por máquinas de Turing se denominan lenguajes no recursivamente enumerables. La opción a) queda descartada.
De acuerdo con la explicación anterior la opción b) realmente es equivalente a la opción a) y por tanto la descartamos.
Respondemos por tanto la opción c).
-
PREGUNTA: Dado el lenguaje L generado por la siguiente gramática:
S -- > xSy | xSyy | z
y el siguiente autómata (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):
(http://i.imgur.com/NJFYt78.jpg)
¿Qué función realiza la pila del autómata en relación a las cadenas del lenguaje L?
a) Lleva la cuenta del número de x's presentes en las cadenas del lenguaje L.
b) Lleva la cuenta del número de y's presentes en las cadenas del lenguaje L.
c) Lleva la cuenta del número de z's presentes en las cadenas del lenguaje L.
d) Lleva la cuenta del número de producciones necesarias para derivar las cadenas del lenguaje L.
RESPUESTA: la opción correcta es la d).
Las cadenas del lenguaje L son
a) xzy, xxzyy, xxxzyyy, … es decir, un cierto número de x´s seguidas de una z y luego el mismo número de z´s que x´s hubieran aparecido previamente.
b) xzyy, xxzyyyy, xxxzyyyyyy … es decir, cierto número de x´s seguido de una z y a continuación el doble número de y´s que de x´s hubieran aparecido previamente.
c) z (cadena mínima admitida por la gramática)
El autómata de la figura es no determinista ya que tiene dos transiciones posibles para una misma entrada y símbolo en cima de pila.
Por la rama de q0-q1 no puede reconocer ninguna cadena de L, ya que tras recibir una x no tiene transición definida para la z, y si recibe una z no llega a aceptación.
Por la rama de q0-q2 la única cadena que puede reconocer es xzy. En este caso al leer la x pone una a en la pila y al leer la z pone otra a en la pila, dejando la pila con dos a´s. Dos a´s no son el número de x´s, de z´s ni de y´s de la cadena. Por tanto descartamos a), b) y c).
¿Cuáles son las producciones necesarias para derivar xyz?
1 S -- > xSy
2 S -- > z
Se deriva xSy y de ahí xzy.
Por tanto la pila ha contado el número de producciones necesarias y respondemos la opción d).
Esta pregunta podemos calificarla de extraña, porque atribuirle un papel a la pila del autómata cuando éste sólo puede reconocer una cadena del lenguaje es un poco… extraño.
Otra forma de razonarlo: cada x implica una producción y cada z implica también una producción. El autómata apila una a con cada x ó cada z, por tanto está contando el número de producciones.
-
PREGUNTA: Dado el alfabeto Σ = {0, 1}, el lenguaje L se define como L = {w | w contiene un número par de 0's, o exactamente dos 1 's }. Indicar qué expresión regular genera el lenguaje L:
a) (1*01*01*0*) + (0*10*10*)
b) (1*01*01*)* + (0*10*10*)
c) (10101)* + (0*10*10*)
RESPUESTA: la opción correcta es la b).
Analizamos la opción a). Nos permite generar 000 y esta cadena no contiene un número par de ceros ni exactamente dos unos, por lo que descartamos la opción a).
Analizamos la opción b). El sumando izquierdo implica que se admite la cadena vacía, que tiene cero 0´s. El número cero se considera par, por tanto se admite. El sumando izquierdo obliga a que el número de ceros sea siempre par si se escoge este sumando. El sumando derecho siempre tiene dos 1´s. Esta expresión regular genera un lenguaje como el indicado.
Analizamos la opción c). El sumando izquierdo implica que se admite la cadena vacía, que tiene cero 0´s. El número cero se considera par, por tanto se admite. En otro caso, el sumando izquierdo siempre tiene un número par de ceros. El sumando derecho es igual que el de la opción b, siempre tiene dos 1´s.
Se podría responder la b) o la c), al menos los lenguajes que generan b) y c) cumplen con los criterios del lenguaje, ahora bien, ¿representan exactamente el lenguaje o a un subconjunto del lenguaje? Para responder esto nos ponemos cadenas mínimas del lenguaje y nos preguntamos qué opción permite generarlas:
Cadena vacía: la generan la opción b) y c).
Cadena 11: la generan la opción b) y c).
Cadena 00: la genera b) pero no la genera c). Por tanto b) representa el lenguaje mientras que c) representa un subconjunto del lenguaje.
Nota: pregunta sutil, hemos de responderla analizando detenidamente las expresiones y recurriendo a cadenas de prueba.
-
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 jun_11_2a_sem_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...
-
Animo a todos los que estén estudiando! Cualquier sugerencia sobre temas de preguntas de examen me pueden escribir por foro o por MP. Sl2
-
Buenas, está súper bien tu aportación de este tema, muchas gracias. Tengo una pregunta que me hicieron en un examen de Teoría de la Computación que me ronda por la cabeza y no soy capaz de contestarla bien, si fueras tan amable de ayudarme...tengo el examen en pocos días y por si pregunta algo similar, me ayudaría un montón. Allí va la pregunta ¿Es posible diseñar un autómata a pila que reconozca un lenguaje de tipo 3? ¿Por qué?
Gracias de antemano.
Un saludo.
-
Hola, si por lenguaje tipo 3 entendemos el tipo 3 que define la jerarquía de Chomsky (https://es.wikipedia.org/wiki/Jerarqu%C3%ADa_de_Chomsky) la respuesta es que sí.
¿Por qué? Porque los lenguajes de tipo 3 en la jerarquía de Chomsky se corresponden con lenguajes regulares obtenibles mediante expresiones regulares. Estos lenguajes son un subconjunto de los lenguajes independientes del contexto que se definen con autómatas a pila.
Saludos
-
Buenos dias y felicitaciones por el trabajo realizado en este foro. Ha sido de gran utilidad para esta Asignatura de Automatas. Muy agradecido.
En relacion a la respuesta #94, mi duda es la siguiente:
¿por que no es posible que la etiqueta 2 sea ε, z; ε? entiendo que al hacer una transicion espontánea desde q1 a q2 consumiendo una z de la cima de la pila, lo que hace es garantizar que al llegar a q2, en la pila tengamos una z menos que las x's leidas, por lo cual aceptará en q2 tantas y's como z's y dara por buena toda cadena de tipo xn+1 yn.
Saludos y mil gracias.
-
Hola, tienes que comprobar que simultáneamente los valores de Etiqueta-1 y Etiqueta-2 permitan cumplir con lo que se quiere. Quizás uno de los dos valores es válido, pero ¿los dos al mismo tiempo lo son? Comprueba haber revisado esto... si encuentras que alguna de las opciones propuestas es válida explica cómo, con la respuesta que he dado yo en el mensaje correspondiente se indica que ni la a) ni la b) resultan válidas. Saludos ;)
-
He actualizado algunas respuestas en base a comentarios que me han hecho llegar varias personas, gracias a todos por vuestra ayuda! (y en especial a klanderblzer)