Extensión a CFG, ¿qué es?

Question

Considere la siguiente extensión de gramáticas libres de contexto que permite que las reglas tengan en el lado izquierdo, uno (o más) terminal en el lado derecho del no terminal. Es decir, reglas de la forma:

A b -> ... 

El lado derecho puede ser cualquier cosa, como en las gramáticas sin contexto. En particular, es no se requiere, que el lado derecho tendrá exactamente el mismo símbolo de terminal al final. En ese caso, esta extensión sería sensible al contexto. Pero la terminal no es solo un contexto. A veces, este terminal se llama "retroceso".

Claramente, esto ya no es CFG (tipo-2). Incluye tipo-1. ¿Pero, qué es esto? ¿Realmente escribes-0 ya?

Esta extensión en particular está permitida en Definite Clause Grammars dcg en Prolog. (Para evitar malentendidos, no considero aquí las extensiones completas de Prolog. Es decir, supongo que las terminales provienen de un alfabeto finito y no son términos arbitrarios, tampoco considero los argumentos adicionales de Prolog que están permitidos en los DCG, que también entran en type- . 0 ya)

---

Editar: Aquí está una manera más sencilla de describir la extensión: Añadir a una CFG reglas de la forma

A b -> <epsilon> 

Answer 1

para responder a mi pregunta con respecto al formalismo DCG de Prolog, esta extensión se llama ahora un semicontext.Ver N253 DIN Draft for DCGs 2014-04-08 - ISO/IEC WDTR 13211-3:2014-04-08

Dada

a1, [b] --> ... . 

a2, [b,b] --> ... . 

El terminal de secuencia [b] es ahora un semicontext, así como el terminal de secuencia [b,b].

¿Sería la misma secuencia terminal de ahora aparecerá al final de la regla, tendríamos un contexto:

a3, [b,b] --> ..., [b,b]. 

Así "semi" significa aquí "medio" - similar a un semigrupo donde la mitad de la algebraica propiedades de un grupo de espera.

Answer 2

Sip su tipo 0 que pienso. El principio para los primeros 3 tipos (3, 2 y 1) es que esos no pueden realizar la reducción. Esos son solo generativos tipos.

Aquí puede transformar un terminal en épsilon por lo que es de tipo 0.

Answer 3

He aquí una respuesta parcial:

La gramática está dentro de tipo 0. Un context-sensitive grammar (tipo 1) tiene reglas de la forma wAx -> wBx donde w yx son cadenas de terminales y no terminales, y B no está vacío. Tenga en cuenta que dado que B no está vacío, |wAx| <= |wBx|. Su gramática tiene reglas de la forma Ax -> z donde z es una cadena de terminales y no terminales y puede estar vacía, y x puede eliminarse. Esto viola dos principios de CSG.

unsatisfyingly, que no respondió dos cosas:

• ¿Es el lenguaje generada por el tipo de gramática-1? La gramática es tipo-0, pero eso no significa que el lenguaje no puede ser de tipo-1. Por ejemplo, los lenguajes regulares (tipo 3) se pueden describir con CFG (tipo 2).

• ¿Es el idioma recursive? Esto es importante ya que, de ser así, el lenguaje es decidible (no sufre el problema de detención).

  Actualmente estoy intentando una prueba para el segundo punto, pero probablemente esté más allá de mi capacidad.