Gramática booleana

Las gramáticas booleanas , introducidas por Okhotin  [Wikidata] , son una clase de gramáticas formales estudiadas en la teoría formal del lenguaje . 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 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 los idiomas. Una clase intermedia de gramáticas conocidas como gramáticas conjuntivas permiten 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}}$

donde es un no terminal, y , ..., , , ..., son cadenas formadas por símbolos en y . De manera informal, dicha regla afirma que cada cadena sobre que satisface 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 . ${\displaystyle A}$ ${\displaystyle m+n\geq 1}$ ${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{m}}$ ${\displaystyle \beta _{1}}$ ${\displaystyle \beta _{n}}$ ${\displaystyle \Sigma }$ ${\displaystyle N}$ ${\displaystyle w}$ ${\displaystyle \Sigma }$ ${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{m}}$ ${\displaystyle \beta _{1}}$ ${\displaystyle \beta _{n}}$ ${\displaystyle A}$

Existen varias definiciones formales del lenguaje generado por una gramática booleana. Tienen una cosa en 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 este sistema. La semántica difiere en los detalles, algunos definen los lenguajes utilizando ecuaciones de lenguaje, algunos se basan en ideas del campo de la programación lógica . Sin embargo, estas cuestiones no triviales de definición formal son en su mayoría irrelevantes para consideraciones prácticas, y uno puede 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 las gramáticas libres de contexto , como los algoritmos de análisis sintáctico 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 fundamentada 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". En Gao, Y.; Lu, H.; Seki, S.; Yu, S. (eds.). Desarrollos en teoría del lenguaje . 14.ª Conferencia internacional, DLT 2010, Londres, ON, Canadá, 17-20 de agosto de 2010, Actas . Apuntes de clase en informática . Vol. 6224. págs. 340-351.Preimpresión disponible en línea, archivado el 3 de marzo de 2016 en Wayback Machine .

Enlaces externos

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