¿Qué significa decir que un lenguaje es libre de contexto?
Respuestas
¿Demasiados anuncios?
A gramática libre de contexto se define como gramática en el que cada regla de producción es de la forma $A \rightarrow \alpha$ , donde $A$ es una variable y $\alpha$ es una secuencia de variables y terminales.
Formalmente, una gramática libre de contexto puede definirse como una 4-tupla $(V, \Sigma, R, S)$ , donde $V$ es un conjunto finito formado por los variables , $\Sigma$ es un conjunto finito formado por los terminales , $R$ es un conjunto de normas de producción (en la forma mencionada anteriormente), y $S \in V$ es el variable inicial .
El lenguaje de una gramática libre de contexto es el conjunto de cadenas que pueden derivarse de su variable de inicio. A lenguaje sin contexto es cualquier lenguaje generado por una gramática libre de contexto.
Por ejemplo, $\{ 0^n1^n : n \ge 0 \}$ es libre de contexto porque está generada por la gramática libre de contexto $(\{S\}, \{0, 1\}, R, S)$ donde el conjunto de reglas, $R$ es $$S \rightarrow 0S1 \mid \varepsilon.$$
(Nota: Estoy utilizando $\varepsilon$ para denotar la cadena vacía o nula).
Como se ve en este ejemplo, el conjunto de lenguajes libres de contexto contiene lenguajes que no son regulares. Además, como es fácil imitar un DFA con una gramática libre de contexto, el conjunto de lenguajes regulares es un subconjunto propio del conjunto de lenguajes libres de contexto. Los autómatas pushdown son los primos autómatas de las gramáticas libres de contexto; aceptan lenguajes libres de contexto y existen algoritmos para convertir entre los dos modelos.
Tenga en cuenta que el lenguaje $\{ a^nb^nc^n : n \ge 0 \}$ es no libre de contexto (intente escribir una gramática libre de contexto para generar este lenguaje y se dará cuenta de por qué). Se puede demostrar que el lenguaje no es libre de contexto con la bombeo-lema para lenguajes libres de contexto que dejaré como ejercicio para el lector.
Hay gramáticas más potentes, como gramáticas sensibles al contexto que permiten que las reglas de producción tengan la forma $\beta A \gamma \rightarrow \beta\alpha\gamma$ , donde $\alpha$ , $\beta$ y $\gamma$ son secuencias de variables y terminales. Las gramáticas sensibles al contexto son tan potentes como los autómatas lineales acotados (LBA).
mxmissile
Puntos
382
Dada la definición técnica de lo que es un lenguaje y lo que es libre de contexto, se significa que en el tratamiento de las reglas que definen el lenguaje no se utiliza el contexto. Es decir, cualquier variable se reescribe por sí misma, sin contexto. Una vez que se produce una variable en una derivación, ninguna de las cadenas que rodean a esa variable intervendrá en ninguna otra derivación... no se utiliza ningún contexto al reescribir una variable.
Los lenguajes más complicados no tienen esta restricción (pueden permitir el uso de contexto/otras variables adyacentes y terminales en la reescritura de una variable).
Los lenguajes libres de contexto son "más fáciles" de analizar (más rápido/más eficiente) que los sensibles al contexto.
Tenga en cuenta que el término "contexto" es muy técnico aquí; se refiere al contexto de una subcadena cuando se reescribe. Los términos técnicos tienen vida propia y no necesariamente se relacionan bien con la primera comprensión lego de la palabra.
jdotjdot
Puntos
129
Otra caracterización es ésta: El conjunto de lenguajes libres de contexto CFL es el conjunto de todos los lenguajes que son aceptados por (quizás no deterministas) autómatas de empuje (autómatas finitos más una pila).
De forma más intuitiva, los lenguajes libres de contexto tienen la propiedad de que las diferentes partes de una palabra son independientes en cierto sentido, es decir, del mismo modo que programación dinámica optimiza los subproblemas de forma independiente. No por casualidad, las gramáticas libres de contexto pueden analizarse mediante programación dinámica ( Algoritmo CYK ), los que no son libres de contexto no pueden (en general).
dani
Puntos
118
