[Ejercicio 4] [Parte 3]

[Ejercicio 4] [Parte 3]

de Martin Sebastian Piñeyro Olivera -
Número de respuestas: 3

Buenas tardes,

Me genera duda si este ejercicio sale enteramente aplicando propiedades de clausura para leng. regulares.

En un caso general, el conjunto de las tiras palíndromas describen un lenguaje no regular. Pero en el caso del ejercicio se sabe que x.x^r pertenece a L regular.

¿Alcanzaría con encontrar un contraejemplo que resulte en un leng. del tipo 0^n1^n?

Se agradece cualquier pique para encararlo!


En respuesta a Martin Sebastian Piñeyro Olivera

Re: Ejercicio 4.3

de Diego Garat -
hola:

me parece que hay una confusión con el lenguaje del ejercicio. las tiras de ese lenguaje no son necesariamente palíndromas, sino que son la primera mitad de una tira palíndroma (de largo par) de un lenguaje regular L.

así, si L es {abab, bbaabb}, el lenguaje de esa parte sería {bba}, pues la tira bba.abb pertenece a L, y es la única ya que abab no es palíndroma y su primera mitad, ab, concatenada con su reverso no pertenece a L.

un ejemplo infinito sería, por ejemplo, el lenguaje L( (ab)*(ba)*). en este caso, el lenguaje es L(ab)*, porque tomando una tira cualquiera (ab)^i, su reverso es (ba)^i, y (ab)^i . (ba)^i pertenece al lenguaje original. observen que hay tiras del lenguaje original que no son de la forma x.x^r, por ejemplo abbaba.

te dejo pensarlo teniendo esta nueva óptica.

saludos,
d.-
En respuesta a Diego Garat

Re: Ejercicio 4.3

de Diego Garat -
además, agrego, no siempre son "propiedades" lo que se aplica. se puede dar como prueba expresiones regulares o autómatas finitos creados a partir de la e.r. o autómata que denota/reconoce a L, como, por ejemplo, sucede para probar que el complemento o el reverso de un lenguaje regular también es regular.