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

[nosferacento]

PREGUNTA: Sea L₁ 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 L₂ = {aⁿbⁿcⁿ : 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 L₂ 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.

[nosferacento]

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… 

[nosferacento]

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

[nosferacento]

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.

[nosferacento]

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

[nosferacento]

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.

[nosferacento]

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.

[nosferacento]

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.

[nosferacento]

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.

[nosferacento]

PREGUNTA: Dada la siguiente máquina podemos afirmar:

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

[nosferacento]

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.

[nosferacento]

PREGUNTA: Dado el siguiente autómata podemos afirmar:

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!

[nosferacento]

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

[nosferacento]

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

[nosferacento]

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.

[nosferacento]

Con lo visto hasta ahora hemos completado un examen, que normalmente consta de diez preguntas tipo test. Es conveniente que se trate de resolver el examen haciendo una simulación de examen real, controlando el tiempo empleado y todas las preguntas a la vez sin consultar ningún tipo de documentación, y luego comprobar cómo nos hubiera ido en ese caso supuesto "real" y qué nota habríamos sacado. Para quien quiera intentarlo, dejo el examen con enunciados completos en el archivo adjunto a este post (archivo sept12_orig_A.pdf, pulsar sobre el nombre o icono para descargarlo estando logeado). Y continuamos...

[nosferacento]

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*(x⁵y²) 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*(x⁷y) 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.

[nosferacento]

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

[nosferacento]

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.

[nosferacento]

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) (aⁿbⁿcⁿ) , 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.