Una pregunta sobre lenguajes libres de contexto del libro de computación de Sipser.

Question

Estoy tratando de aprender algo de la teoría de la computabilidad, y me encontré con una pregunta en Sipser del libro que no puedo entender. El ejercicio pide a mostrar que existe un algoritmo que acepte una gramática independiente del contexto $G$ y decidir si o no $\{1\}^*$ es un subconjunto del lenguaje generado por $G$. Yo estaba tratando de hacer algún tipo de bombeo, mientras que busca patrones en el contenido de la pila, pero no pude hacerlo funcionar. Después de examinar la pila de contenidos, ¿hay algún tipo de longitud máxima después de que usted puede detener la comprobación de cualquier cadena más larga de 1? Cualquier sugerencia se agradece.

Answer 1

Este interesante problema parece no tener solución simple. Está ligado al hecho de que unario contexto libre de idiomas (es decir, a través de una sola letra del alfabeto) en realidad son regulares. Este es un muy avanzada aplicación de bombeo, un caso especial de Parik del Teorema. Para regular los idiomas de la propiedad es decidable. Esto debe ser contrastado con las dos letras para el caso (¿se puede generar cada cadena en $\{0,1\}^*$) que es indecidible/

Answer 2

¿Realmente nadie se molestó en leer el libro / esta pregunta? El problema no requiere un CFG de DFA que reconozca este lenguaje, sino una prueba de que este lenguaje es decidible, es decir, existe un TM que siempre se detiene y determina si algún CFG / DFA arbitrario acepta todas las cadenas en 1 *.

La prueba de que este lenguaje es decidible está aquí.

Answer 3

Para un problema como este, es más fácil trabajar con la CFG que con la PDA. Debe comenzar en el terminal$1$ y volver a la variable de inicio$S$. Al reemplazar las variables con terminales, eventualmente querrá mostrar que la regla

$S \rightarrow \epsilon \; |\; 1S\; |\;S1$

Existe en el CFG.