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

PREGUNTA: Dado el lenguaje L = {xⁿyⁿ : 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.




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

Gracias a todos los que hacéis llegar comentarios y sugerencias, así al menos puedo saber que todo esto está sirviendo para algo 

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:


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.

PREGUNTA: Sea el lenguaje L = {xⁿy^m : 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.


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: 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: ¿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: El lema del bombeo aplicado a los autómatas a pila demuestra que el lenguaje L = {xⁿyⁿzⁿ : 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:  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:


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 2ⁿ 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:


En este caso estamos en el caso “mejor”: no se ha incrementeado el número de estados respecto del AFN.