Diferencia entre la gramática regular y el CFG en la generación de historiales de computación y $ \ SIGMA ^ * $

Question

Me gustaría solicitar la intuición para comprender la diferencia entre un CFG generando $ \ sigma ^ * $ y una gramática regular generando $ \ sigma ^ * $ .. Tengo los ejemplos aquí de Sipser. Deje que $ all_ {cfg} $ se refiere al idioma que un CFG determinado genera $ \ sigma ^ * $ y deje que $ all_ {rex} $ se refiere al idioma que una expresión regular dada genera $ \ sigma ^ * $ < / SPAN> (y como para cada expresión regular hay una gramática regular, también podemos decir que la gramática regular equivalente genera $ \ sigma ^ * $ ).

de lo que tengo, tenemos:

• $ all_ {cfg} $ no es decidible, tampoco es reconocible. Deje que $ \ overline {a_ {tm}} $ consulte el idioma que un TM $ M $ hace No acepte la palabra de entrada $ w $ . Podemos reducir $ \ overline {a_ {tm}} $ a $ all_ {cfg} $ en polinomio Tiempo usando historias de cálculo. La reducción construye un CFG que genera todas las palabras posibles donde: 1) Los primeros caracteres no coinciden $ w $ , 2) Los últimos caracteres no coinciden con la aceptación de configuraciones, y 3) Los caracteres no coinciden con transiciones válidas de $ m $ 's configuraciones. Por lo tanto, $ A_ {TM} $ no acepta $ w $ iff El CFG genera $ \ SIGMA ^ * $ (es decir, no hay historiales de cálculo de aceptación). Dado que los mapas de reducción $ \ overline {a_ {tm}} $ a $ all_ {cfg} $ , y $ \ overline {a_ {tm}} $ no es reconocible, $ all_ {cfg} $ no es tutor-reconocible.

• $ all_ {rex} $ es decidible ya que es decidible si un automatón finito acepta $ \ sigma ^ * $ . Sin embargo, el problema de aceptación para cualquier idioma regular $ r $ se puede reducir polinomialmente al idioma $ all_ {rex} - f (R_m) $ , donde $ r_m $ es un TM que decide $ r $ , y $ f (r_m) $ es una reducción similar de las historias de cómputo como se describe anteriormente. Con más detalle, $ f (r_m) $ es la gramática regular que genera todas las palabras posibles donde 1) los primeros caracteres no coinciden con $ W $ , 2) Los últimos caracteres no coinciden con las configuraciones de rechazo, y 3) caracteres no coinciden con transiciones válidas de $ r_m $ 's configuraciones. El Decider para $ all_ {rex} - f (r_m) $ verifica si está vacío (lo que significa que $ f ( R_M) $ es igual a $ \ sigma ^ * $ ). Si está vacío, no hay rechazamiento de historiales de cálculo y $ w \ en R $ . (En Sipser, usó algo como esto para mostrar la integridad de EXPSPACE-integridad para $ all_ {rex} - f (r_m) $ )

Me gustaría preguntar:

Desde arriba, ambas gramáticas regulares y CFG podrían generar historiales de cálculo de un TM, y ambos podrían generar $ \ sigma ^ * $ . Pero, ¿qué es con el poder fundamental de la gramática de CFG que lo hace válido para reducir el $ \ overline {a_ {tm}} $ a $ all_ {cfg} $ , pero no es posible para $ \ endinline {a_ {tm}} $ para reducir a $ all_ {rex} - f (A_ {tm}) $ ? Sé que no podemos reducir $ \ overline {a_ {tm}} $ a $ all_ {rex} - f (A_ {Tm}) $ desde $ all_ {rex} - f (A_ {tm}) $ es decidible, mientras que $ \ Overline {A_ {TM}} $ no es reconocible ... pero me gustaría comprender esto en términos de la diferencia en la generación de energía entre las gramáticas de CFG y regulares a través de sus reglas.

Por ejemplo, de lo que leí, el permiso de CFG las reglas $ a \ rudowarrow bc $ , donde $ b $ y $ C $ son cadenas de variables y terminales. Por otro lado, las gramáticas regulares solo permiten las reglas en forma de

-Container "> $ A \ Rudowarrow AB $ , donde $ a $ es un terminal. Me gustaría preguntar: ¿Por qué incorpora las reglas de la forma? $ A \ Rudowarrow BC $ a una gramática, dale suficiente energía de la generación de tal manera que ya sea válida para reducir $ \ overline{A_ {tm}} $ a la gramática (es decir, a la CFG).

Answer 1

Su resumen de la prueba de la indifetabilidad no es precisa. Su especificación de $ \ overline {A_ {tm}} $ no es correcto.

Para una exposición razonable de la prueba, consulte https://liacs.leidenuniv .nl / ~ HOOGEBOOMHJ / SEGUNDO / CODINGPUTACIONES.PDF Particularmente el comienzo de la Sección 1 y la Sección 3.

La intuición no es fácil de transmitir, ya que la prueba no es del todo trivial. Pero aquí está el hecho principal. Deje que $ V, W $ sean dos configuraciones de una máquina de Turing. Escribe $ n (v) $ Para ser la siguiente configuración de la máquina de Turing después de un solo paso del cálculo, si comienza en la configuración $ v $ . Definir el idioma

$$ l={v \ # w ^ r \ mid n (v) \ ne w \}. $$

Entonces, el hecho clave es que $ l $ está libre de contexto. Esto toma algunas pruebas; demostrando que es un paso clave en la prueba. Sin embargo, esa es la respuesta a su pregunta: $ l $ es libre de contexto pero no regular. Como resultado, podemos reducir el problema de detención a $ all_ {cfg} $ pero no $ all_ {rex} $ .

He omitido muchos pasos para darle una descripción general de la idea principal. Deberá leer la prueba completa para completar los detalles. Sugiero que usted siga leyendo y comprenda la prueba, con esta perspectiva en mente, y luego revise lo que he escrito aquí. Esperemos que eso lo ayude a comprender por qué la prueba tiene lenguajes libres de contexto, pero fallaría por idiomas regulares.

Answer 2

La diferencia entre los modelos se deriva, intuitivamente, de la capacidad de CFGS a CUENTA . Más precisamente, CFGS puede generar cadenas de la forma $ a ^ nb ^ n $ , donde el número de $ a $ 's y $ b $ ' s es el mismo.

Esta habilidad le otorga la potencia de comparar cuerdas, que luego se pueden utilizar para mostrar la indecisión, ya que el CFG es capaz de comparar los contenidos de una cinta entre dos configuraciones consecutivas.

Esto se hace un poco más evidente si recuerda que el problema de detención de máquinas de dos mostradores (máquinas MINSKY) no es decidida. Allí, se proporciona una configuración por los valores de dos contadores. Puede esto de esto como un TM con una especie de alfabeto unario (aunque no exactamente). En dos máquinas de mostrador, comparando dos configuraciones consecutivas cantidades exactamente para comparar los valores de los contadores en pasos consecutivos, que es justo en el callejón para CFGS.

En contraste, los idiomas regulares son capturados por Finite State Automata, que tienen memoria finita, y pueden contar solo hasta un número fijo. Por lo tanto, estos autómatas pueden simular un TM siempre que la longitud de una configuración esté limitada por adelantado. ¿Por qué esto nos da la dureza de PSPACE? Bueno, puede simularlo CUALQUIER TM que funciona en el espacio limitado, no tiene que ser polinomial en la entrada. Sin embargo, para que la reducción sea polinomial, necesita que el límite sea polinomial. Por lo tanto, obtienes exactamente la dureza de PSPACE.

Con respecto al "tipo" de las reglas, no es tanto el $ A \ a bc $ reglas que son un problema, es más en las reglas de la Forma $ A \ a AAB $ (o de manera más general, la capacidad de tener reglas cíclicas . La razón es que $ A \ a bc $ tiene una estructura de "árbol", y si $ b $ y $ C $ no están relacionados más adelante, entonces esto es efectivamente una operación sindical, que pueden simular idiomas regulares.

Sin embargo, una regla de la forma $ A \ a AAB $ mantiene el "contexto" $ a $ , que es algo que los idiomas regulares no pueden hacer.

para resumir:

semánticamente, el poder de los CFGS radica en su capacidad para contar.

Sintácticamente, el poder de CFGS se encuentra en las reglas cíclicas.