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

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