algorithm - resueltos - gramatica libre de contexto java
Gramáticas libres de contexto versus gramáticas sensibles al contexto (3)
Como se dijo anteriormente, una Gramática no acepta una cadena, pero es simplemente una manera 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 agrupan en el conjunto de cadenas del lenguaje CS. Espero que mi explicación sea clara.
¿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
La gramática libre de contexto es una gramática formal en la que cada regla de producción (reescritura) es una forma de V → w donde V es un símbolo único no terminal yw es una cadena de terminales y / o no terminales. w puede estar vacío
La gramática sensible al contexto es una gramática formal en la que los lados izquierdo y derecho de cualquier regla de producción (reescritura) pueden estar rodeados por un contexto de símbolos terminales y no terminales.
Pero, ¿cómo puedo explicar por qué esta gramática acepta una cadena?
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 dada y dice "sí" o "no".
Una gramática libre de contexto (CFG) es una gramática donde (como ha notado) cada producción tiene la forma A → w, donde A es un no terminal yw 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.
Una gramática sensible al contexto (CSG) es una gramática en la que cada producción tiene la forma wAx → wyx, donde w y x 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 autómata pushdown (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 autómata lineal limitado (LBA).
Sin embargo, estos enfoques anteriores, si se los trata 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 LL(k) o LR(k) construidos para ellas, 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 el analizador de Earley , que en O (n 3 ) puede determinar si una cadena de longitud n está contenida en la gramática (curiosamente, puede analizar cualquier CFG inequívoco en O (n 2 ), 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 árbol de análisis sintáctico ), 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 Parsing Techniques: A Practical Guide (consulte a continuación) han creado una fantástica página que contiene todo tipo de algoritmos de análisis , incluido uno que analiza los idiomas contextuales.
Si está interesado en aprender más sobre el análisis, considere consultar el excelente libro " Técnicas de análisis: una guía práctica, segunda edición " 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!
Una manera fácil de mostrar que una gramática acepta una cadena es mostrar las reglas de producción para esa cadena.