Gramáticas libres de contexto versus gramáticas sensibles al contexto?

Question

¿Puede alguien explicarme por qué las gramáticas [gramática libre de contexto y la gramática sensible al contexto] de este tipo aceptan una cadena?

Lo que sé es

gramática independiente del contexto es una gramática formal en el que cada producción (reescribir) regla es una forma de V → W Donde V es un único símbolo no terminal y W es una cadena de terminales y/o no terminales. w puede estar vacío

gramática sensible al contexto es una gramática formal en el que los lados de la izquierda y los lados de la mano derecha de cualquier producción (reescribir) reglas pueden estar rodeadas por un contexto de terminal y símbolos no terminales.

Pero, ¿cómo puedo explicar por qué esta gramática acepta una cadena?

Answer 1

Una manera fácil de mostrar que una gramática acepta una cadena es mostrar las reglas de producción para esa cadena.

Answer 2

Un detalle importante aquí es que las gramáticas no aceptan cadenas; ellos generan cadenas. Las gramáticas son descripciones de idiomas que proporcionan un medio para generar todas las cadenas posibles contenidas en el idioma. Para saber si una cadena en particular está contenida en el idioma, usaría un reconocedor, una especie de autómata que procesa una cadena determinada y dice "sí" o "no".

A context-free grammar (CFG) es una gramática donde (como se anotó) cada producción tiene la forma A → w, donde A es un no terminal y w es una cadena de terminales y no terminales. Informalmente, un CFG es una gramática donde cualquier no terminal puede expandirse a cualquiera de sus producciones en cualquier punto. El lenguaje de una gramática es el conjunto de cadenas de terminales que se pueden derivar del símbolo de inicio.

A context-sensitive grammar (CSG) es una gramática en la que cada producción tiene la forma wAx → wyx, donde w yx son cadenas de terminales y no terminales, y y es también una cadena de terminales. En otras palabras, las producciones dan reglas que dicen "si ves A en un contexto dado, puedes reemplazar A por la cadena y". Es desafortunado que estas gramáticas se denominen "gramáticas sensibles al contexto" porque significa que "sin contexto" y "sensibles al contexto" no son opuestos, y eso significa que hay ciertas clases de gramáticas que podrían tener una gran cantidad de contexto información en la cuenta pero no se considera formalmente que sea sensible al contexto.

Para determinar si una cadena está contenida en un CFG o un CSG, hay muchos enfoques. Primero, podrías construir un reconocedor para la gramática dada. Para los CFG, el pushdown automaton (PDA) es un tipo de autómata que acepta precisamente los idiomas sin contexto, y hay una construcción simple para convertir cualquier CFG en un PDA. Para las gramáticas sensibles al contexto, el autómata que usaría se llama linear bounded automaton (LBA).

Sin embargo, estos enfoques anteriores, si se tratan ingenuamente, no son muy eficientes. Para determinar si una cadena está contenida en el lenguaje de un CFG, existen algoritmos mucho más eficientes. Por ejemplo, muchas gramáticas pueden tener analizadores LL(k) o LR(k) construidos para ellos, lo que le permite (en tiempo lineal) decidir si una cadena está contenida en la gramática.Todas las gramáticas se pueden analizar utilizando Earley parser, que en O (n) puede determinar si una cadena de longitud n está contenida en la gramática (curiosamente, puede analizar cualquier CFG inequívoco en O (n), y con lookaheads puede analizar cualquier gramática LR (k) en el tiempo O (n)!). Si estuvieras completamente interesado en la pregunta "¿está contenida la cadena x en el lenguaje generado por la gramática G?", Entonces uno de estos enfoques sería excelente. Si desea saber cómo se generó la cadena x (al encontrar un parse tree), puede adaptar estos enfoques para proporcionar también esta información. Sin embargo, el análisis de CSG es, en general, PSPACE completo, por lo que no hay algoritmos de análisis conocidos para ellos que se ejecuten en el peor tiempo de polinomio. Sin embargo, hay algunos algoritmos que en la práctica tienden a ejecutarse rápidamente. Los autores de Técnicas de análisis: una guía práctica (ver a continuación) han reunido a fantastic page containing all sorts of parsing algorithms, incluido uno que analiza los idiomas contextuales.

Si está interesado en aprender más sobre el análisis, considere consultar el excelente libro "Parsing Techniques: A Practical Guide, Second Edition" de Grune y Jacobs, que analiza todo tipo de algoritmos de análisis para determinar si una cadena está contenida en una gramática y, si es así. , cómo es generado por el algoritmo de análisis.

Espero que esto ayude!

Answer 3

Como se dijo anteriormente, una Gramática no acepta una cadena, pero es simplemente una forma de generar palabras específicas de un Idioma que usted analiza. De hecho, la gramática como regla generativa en la teoría del lenguaje formal en lugar del autómata de estado finito hace lo que usted dice, el reconocimiento de cadenas específicas. En particular, necesita un autómata enumerable recursivo para reconocer Lenguajes Tipo 1 (los Lenguajes Sensibles al Contexto en la Jerarquía de Chomsky). Una gramática para un idioma específico solo le otorga la especificación de la propiedad de todas las cadenas que se reúnen en el conjunto de cadenas del lenguaje CS. Espero que mi explicación sea clara.