¿A qué se refiere “contexto” en “gramática libre de contexto”?

Hay muchas definiciones en línea sobre lo que es una gramática libre de contexto, pero nada de lo que encuentro satisface mi problema principal:

¿De qué contexto está libre?

Para investigar, busqué en Google "gramática sensible al contexto" pero todavía no pude encontrar de qué se trataba el "contexto".

¿Alguien puede explicar a qué contextse refiere el término en estos nombres?

terminology context-free formal-grammars CodyBugstein
fuente

Creo que la explicación de Wikipedia es bastante buena: "Una gramática formal se considera" libre de contexto "cuando sus reglas de producción se pueden aplicar independientemente del contexto de un no terminal. No importa qué símbolos lo rodeen, el único no terminal en el lado izquierdo siempre puede ser reemplazado por el lado derecho ". - puede reformularse y simplificarse para convertirse en "Inglés simple", pero la esencia de esto me parece bastante clara.

jkff

@jkff es genial que la explicación te parezca buena, pero todavía no entiendo qué significa realmente "contexto" aquí. Necesito ver un ejemplo donde hay contexto y donde no hay contexto. Para mí, parece que cada gramática que he visto tiene contexto

CodyBugstein

¿No está claro a partir de la definición?

Raphael

Irónicamente, el contexto crucial faltaba en esa definición , así que solo agregué una oración para explicarlo.

reinierpost

Ejemplo: en C ++ 11, overridepuede ser un nombre de variable o una palabra clave, dependiendo de dónde se use (es decir, su contexto). Si se usa después de una declaración de método, es una palabra clave. De lo contrario no lo es. Este es un ejemplo de una gramática sensible al contexto.

Thomas Eding

Respuestas:

Tienes razón, siempre hay un contexto en algún sentido. No creo que puedas entender qué significa "contexto" en "sin contexto" sin entender una producción.

Una producción es una regla de sustitución. Dice que, para generar cadenas dentro del lenguaje, puede sustituir lo que está a la izquierda por lo que está a la derecha:

A -> xy

Esto significa que la secuencia abstracta A puede ser reemplazada por el carácter "x" seguido por el carácter "y". También puedes tener producciones más complejas:

zA -> xy

Esto significa que el carácter "z" seguido de la secuencia abstracta A puede ser reemplazado por los caracteres "x" e "y".

Una producción sin contexto simplemente significa que solo hay una cosa en el lado izquierdo. El primer ejemplo no tiene contexto, porque A puede ser reemplazado por "x" e "y" sin importar lo que ocurra antes o después. Sin embargo, en el segundo ejemplo, el carácter "z" tiene que aparecer antes de la A, y luego la combinación se puede reemplazar por "x" e "y", por lo que hay algún contexto involucrado.

Una gramática libre de contexto es solo una gramática con solo producciones libres de contexto.

El segundo ejemplo es en realidad un ejemplo de una producción sin restricciones. Hay otra categoría que está entre libre de contexto y sin restricciones llamada "sensible al contexto". Un ejemplo de producción sensible al contexto es:

zA -> zxy

La diferencia es que lo que viene antes de A (y después) en el lado izquierdo debe conservarse a la derecha. Esto efectivamente significa que solo A está sustituido, pero solo puede ser sustituido en el contexto apropiado.

Vaughn Cato
fuente

¡Gracias, es de gran ayuda! En realidad, nunca he visto un ejemplo de gramática con más de una variable en el lado izquierdo como lo mostraste. Supongo que por eso no pude ver cuál era el "contexto". Gracias

CodyBugstein

Quizás un ejemplo contextual más simple sería zA -> zxy: A todavía se reemplaza por xy, pero solo después de z.

MSalters

Con más detalle, esta respuesta habla de una gramática irrestricta , mientras que @MSalters señala que la gramática sensible al contexto sería un mejor ejemplo del significado del contexto.

@MSalters: Tienes un buen punto. Modifiqué mi respuesta. Me costó encontrar una forma de agregar esos detalles a mi descripción sin que parezca más complejo, así que lo que terminé haciendo fue agregar más detalles al final.

Vaughn Cato

Considere la regla y digamos que tiene una forma entonces A reducir a β no depende de qué son α y δ. De esta forma, no tiene contexto, ya que no depende del contexto circundante.

A \to β

$A \rightarrow \beta$

α A δ

$αAδ$

iLoveCamelCase
fuente

¿Qué es beta? ¿Es un terminal o una variable? ¿Y puedes explicar la "forma de sentencia"? ¿Eso significa que no se puede derivar más?

CodyBugstein

Beta puede ser cualquier cosa, es solo que A-> beta es una regla. La forma oracional significa que dado su símbolo de inicio usando las reglas gramaticales, lo transformamos en un resultado. Este resultado se llama forma sentencial. Después de cada uso de cada regla, obtenemos una nueva forma de sentencia.

iLoveCamelCase

@ Imray Debe ir a ver las definiciones formales de las gramáticas y las gramáticas sin contexto. No hay atajos para comprender los objetos formales .

Raphael

@Imray Una forma oracional es una cadena de símbolos terminales y no terminales que deriva del axioma (también llamado símbolo inicial ) mediante la aplicación de reglas gramaticales (también llamadas producciones ). Una forma sentencial puede derivarse en otra aplicando una regla a uno de sus símbolos no terminales. Cuando no quedan terminales que no sean terminales, la forma enunciativa es una oración , es decir, una cadena o palabra en el lenguaje definido o generado por la gramática. La terminología proviene de los lingüistas que en algún momento fueron los principales contribuyentes a esta parte de la teoría del lenguaje formal.

babou

Pensé que una forma sentencial no puede tener ninguna variable, debe ser solo terminales.

CodyBugstein