Éste ejercicio plantea una propiedad que todo LLC reconocible por APD determinista por stack vacío debe cumplir.
Me quedan las siguientes dudas:
1) Si bien es cierto que el reciproco del enunciado del ejercicio no se cumple ya que puede haber lenguajes recursivamente enumerables (y no libres de contexto) que cumplan la propiedad de los prefijos pero que al no ser libres de contexto no existe un APD (de ningún tipo) que los reconozca, me queda la duda de si dado un lenguaje L, el cual sabemos de antemano que es libre de contexto, si además L cumple la propiedad de los prefijos, ¿entonces hay un APD determinista que reconoce L por stack vacío?
2) Pensando en porqué el enunciado es con APD deterministas por stack vacío y no APD deterministas en general (stack vacío o estado final) me surgió otra duda. El contrareciproco del enunciado puede usarse para demostrar que un cierto lenguaje no puede ser reconocido por un APD determinista por stack vacío, pero ¿puede también decirse que el lenguaje no es reconocible por APDs deterministas por estado final?
Habiéndome hecho esa pregunta intenté construir un APD determinista por stack vacío a partir de uno por estado final y vice versa, la idea es que si fuese posible construir un APD determinista por stack vacío a partir de uno por estado final, entonces por contrareciproco de la propiedad mostrada se tiene que:
L no cumple propiedad de los prefijos ==> no hay APD determinista por stack vació que reconozca L ==> no hay APD determinista por estado final que reconozca L (la segunda implicación se debe a que si hubiese uno por estado final entonces construiríamos uno por stack vacío equivalente a partir del que es por estado final y entonces por el directo de la propiedad, L debería cumplir la propiedad de los prefijos, lo cual es absurdo porque se parte de que no se cumple).
Esto respondería mi pregunta de si ¿puede también decirse que el lenguaje no es reconocible por APDs deterministas por estado final?, pero el problema es que no logré construir un APD determinista por stack vacío a partir de uno por estado final sin introducir el no determinismo (sólo pude hacerlo en el sentido opuesto lo cual no resuelve mi duda).
3) La segunda parte del ejercicio creo que llegué a la conclusión correcta:
Si el APD reconoce por stack vacío y es no determinista, entonces L no tiene porque cumplir la propiedad de los prefijos, un ejemplo sería que el lenguaje de peréntesis balanceados es reconocido por un APD por stack vacío no determinista y () es prefijo propio de ()(), por lo que la propied no se sigue cumpliendo.