Las gramáticas booleanas , introducidas por Okhotin gramáticas formales estudiadas en la teoría del lenguaje formal . Extienden el tipo básico de gramáticas, las gramáticas libres de contexto , con operaciones de conjunción y negación . Además de estas operaciones explícitas, las gramáticas booleanas permiten la disyunción implícita representada por múltiples reglas para un solo símbolo no terminal, que es el único conectivo lógico expresable en gramáticas libres de contexto. La conjunción y la negación se pueden utilizar, en particular, para especificar la intersección y el complemento de lenguajes. Una clase intermedia de gramáticas conocida comoLas gramáticas conjuntivas permiten la conjunción y la disyunción, pero no la negación.
, son una clase deLas reglas de una gramática booleana tienen la forma
dónde es un no terminal, y , ..., , , ..., son cadenas formadas por símbolos en y . De manera informal, tal regla afirma que cada cadena encima que satisfaga cada una de las condiciones sintácticas representadas por , ..., y ninguna de las condiciones sintácticas representadas por , ..., por lo tanto satisface la condición definida por .
Existen varias definiciones formales del lenguaje generadas por una gramática booleana. Tienen una cosa en común: si la gramática se representa como un sistema de ecuaciones del lenguaje con unión, intersección, complementación y concatenación, los lenguajes generados por la gramática deben ser la solución de este sistema. La semántica difiere en detalles, algunos definen los lenguajes usando ecuaciones del lenguaje, algunos se basan en ideas del campo de la programación lógica . Sin embargo, estas cuestiones no triviales de la definición formal son en su mayoría irrelevantes para consideraciones prácticas, y se pueden construir gramáticas de acuerdo con la semántica informal dada. Las propiedades prácticas del modelo son similares a las de las gramáticas conjuntivas , mientras que las capacidades descriptivas se mejoran aún más. En particular, se conservan algunas propiedades prácticamente útiles heredadas de gramáticas libres de contexto , como los algoritmos de análisis eficientes, véase Okhotin (2010) .
Referencias
- Okhotin, Alexander (10 de octubre de 2004). "Gramáticas booleanas". Información y Computación . 194 (1): 19–48. doi : 10.1016 / j.ic.2004.03.006 .
- Okhotin, Alexander (2006). Nueve problemas abiertos sobre gramáticas conjuntivas y booleanas (PDF) (Informe técnico). TUCS. 794.
- Kountouriotis, Vassilis; Nomikos, Christos; Rondogiannis, Panos (2009). "Semántica bien fundada para gramáticas booleanas" (PDF) . Información y Computación . 207 (9): 945–967. doi : 10.1016 / j.ic.2009.05.002 .
- Okhotin, Alexander (2010). "Análisis rápido de gramáticas booleanas: una generalización del algoritmo de Valiant", Conferencia Internacional sobre Desarrollos en Teoría del Lenguaje (DLT 2010), Lecture Notes in Computer Science 6224, pp. 340-351. Preimpresión disponible en línea.