gramática booleana

Las gramáticas booleanas , introducidas por Okhotin , son una clase de 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 único símbolo no terminal, que es el único conector lógico expresable en las gramáticas libres de contexto. La conjunción y la negación pueden utilizarse, en particular, para especificar la intersección y el complemento de lenguajes. Una clase intermedia de gramáticas, conocida como gramáticas conjuntivas, permite la conjunción y la disyunción, pero no la negación.

Las reglas de una gramática booleana son de la forma

${\displaystyle A\to \alpha _{1}\And \ldots \And \alpha _{m}\And \lnot \beta _{1}\And \ldots \And \lnot \beta _{n}}$

dónde${\displaystyle A}$es un no terminal,${\displaystyle m+n\geq 1}$y${\displaystyle \alpha _{1}}$, ...,${\displaystyle \alpha _{m}}$,${\displaystyle \beta _{1}}$, ...,${\displaystyle \beta _{n}}$son cadenas formadas por símbolos en${\displaystyle \Sigma }$y${\displaystyle N}$. De manera informal, dicha regla afirma que cada cadena${\displaystyle w}$encima${\displaystyle \Sigma }$que satisface cada una de las condiciones sintácticas representadas por${\displaystyle \alpha _{1}}$, ...,${\displaystyle \alpha _{m}}$y ninguna de las condiciones sintácticas representadas por${\displaystyle \beta _{1}}$, ...,${\displaystyle \beta _{n}}$Por lo tanto, satisface la condición definida por${\displaystyle A}$.

Existen varias definiciones formales del lenguaje generado por una gramática booleana. Todas comparten una característica común: si la gramática se representa como un sistema de ecuaciones de lenguaje con unión, intersección, complementación y concatenación, los lenguajes generados por la gramática deben ser la solución de dicho sistema. La semántica difiere en los detalles; algunas definen los lenguajes mediante ecuaciones de lenguaje, mientras que otras recurren a 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 es posible 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 útiles en la práctica, heredadas de las gramáticas libres de contexto , como algoritmos de análisis sintáctico eficientes (véase Okhotin, 2010) .

• 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 fundamentada para gramáticas booleanas" (PDF) . Information and Computation . 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". En Gao, Y.; Lu, H.; Seki, S.; Yu, S. (eds.). Developments in Language Theory . 14.ª Conferencia Internacional, DLT 2010, London, ON, Canadá, 17-20 de agosto de 2010, Actas . Lecture Notes in Computer Science . Vol.  6224. pp. 340-351 . Versión preliminar disponible en línea, archivada el 3 de marzo de 2016 en Wayback Machine .

• La página de Okhotin sobre gramáticas booleanas