Gramática sensible al contexto

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de enero de 2016; las comprobaciones requieren 10 ediciones .

Una gramática dependiente del contexto ( KZ-grammar , context grammar ) es un caso especial de una gramática formal (tipo 1 según la jerarquía de Chomsky ), en la que las partes izquierda y derecha de todas las producciones pueden estar rodeadas de terminales y no terminales. simbolos

Un caso especial de gramática formal es también la gramática libre de contexto .

Un idioma que se puede especificar mediante una gramática CV se denomina lenguaje dependiente del contexto o lenguaje CV.

Formal definición

Una gramática formal G=(N, T, I, P) es sensible al contexto si todas las reglas de P son de la forma: αAβ → αωβ

donde A ∈ N (es decir, un solo símbolo no terminal), ω ∈ (N ∪ T) + (es decir, una cadena no vacía que consta de símbolos terminales y/o no terminales), α, β ∈ ( N ∪ T)* (es decir, cualquier cadena que consta de caracteres terminales y/o no terminales).

Ejemplos

La siguiente gramática especifica un lenguaje sensible al contexto : $\{a^{n}b^{n}c^{n}:n\geq 1\}$

$S\rightarrow aSBC$
$S\rightarrow aBC$
$CB\rightarrow CZ$
$CZ\rightarrow WZ$
$WZ\rightarrow WC$
$WC\rightarrow BC$
$aB\flecha derecha ab$
$bB\flecha derecha bb$
$bC\flecha derecha bc$
$cC\rightarrow cc$

Así es como se ve la cadena de generación aaa bbb ccc:

S

\Rightarrow _{1}aSBC

\Rightarrow _{1}a{\boldsymbol {aSBC}}BC

\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC

\Rightarrow _{3}aaaB{\boldsymbol {CZ}}CBC

\Rightarrow _{4}aaaB{\boldsymbol {WZ}}CBC

\Rightarrow _{5}aaaB{\boldsymbol {WC}}CBC

\Rightarrow _{6}aaaB{\boldsymbol {BC}}CBC

\Rightarrow _{3}aaaBBC{\boldsymbol {CZ}}C

\Rightarrow _{4}aaaBBC{\boldsymbol {WZ}}C

\Rightarrow _{5}aaaBBC{\boldsymbol {WC}}C

\Rightarrow _{6}aaaBBC{\boldsymbol {BC}}C

\Rightarrow _{3}aaaBB{\boldsymbol {CZ}}CC

\Rightarrow _{4}aaaBB{\boldsymbol {WZ}}CC

\Rightarrow _{5}aaaBB{\boldsymbol {WC}}CC

\Rightarrow _{6}aaaBB{\boldsymbol {BC}}CC

\Rightarrow _{7}aa{\boldsymbol {ab}}BBCCC

\Rightarrow _{8}aaa{\boldsymbol {bb}}BCCC

\Rightarrow _{8}aaab{\boldsymbol {bb}}CCC

\Rightarrow _{9}aaabb{\boldsymbol {bc}}CC

\Rightarrow _{10}aaabbb{\boldsymbol {cc}}C

\Rightarrow _{10}aaabbbc{\boldsymbol {cc}}

Véase también

Simulador de autómatas multiplataforma JFLAP , máquinas de Turing, gramática, dibujo de gráficos de autómatas

Literatura

Cook D., Baze G. Capítulo 8. Lenguajes y gramáticas // Matemáticas informáticas = Matemáticas informáticas. - M. : Ciencia. Fizmatlit, 1990. - 384 p. — ISBN 5-02-014216-6 .

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami