Examen diciembre 2013 ejercicio 1-b

Re: Examen diciembre 2013 ejercicio 1-b

de Luis Sierra -
Número de respuestas: 0

distingamos dos cosas: una cosa es el lenguaje definido (el conjunto de palabras de las que hablamos) y otra cómo lo definimos. cuando decimos Sigma^* como lenguaje es fácil: es el conjunto de palabras que se forman con letras de Sigma. cuando decimos Sigma^* como definición nos referimos a la definición usual que menciona andrés.

el lenguaje definido por la escritura alternativa que plantea carolina, llamémosle L, está perfectamente definido, salvo por la objeción de andrés. carolina tendría aún la tarea de mostrar que L y Sigma^* son el mismo lenguaje. es decir, le falta probar que
(All w : w in Sigma^* : w in L)
y
(All w : w in L : w in Sigma^*)
dos pruebas inductivas me parecen la forma más simple de terminar con esa discusión.

en fin, la definición de un lenguaje L que propone carolina es correcta. pero la suposición de que ese L coincide con Sigma^* no está justificada.

saludos

luis

ps. igualmente, eso no quita que no es una alternativa válida para el ejercicio, ya que la definición de L no es libre.