Gramática booleana

Las gramáticas booleanas, introducidas por Okhotin, son una clase de gramáticas formales estudiadas en la teoría de lenguajes formales. Esta gramáticas 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 la única conectividad lógica expresable en gramáticas libres de contexto. La conjunción y la negación pueden usarse, en particular, para especificar la intersección y el complemento de los idiomas. Una clase intermedia de gramáticas conocidas como gramáticas conjuntivas permite la conjunción y la disyunción pero no la negación.

Las reglas de una gramática booleana tienen la forma

$A\to {\alpha }_1\mathrm{\&}\dots \mathrm{\&}{\alpha }_m\mathrm{\&}\mathrm{\neg }{\beta }_1\mathrm{\&}\dots \mathrm{\&}\mathrm{\neg }{\beta }_n$

dónde $A$ es un no-terminal, $m+n\ge 1$ y ${\alpha }_1$, ..., ${\alpha }_m$, ${\beta }_1$, ..., ${\beta }_n$ son cadenas formadas de símbolos en $\mathrm{\Sigma }$ y $N$. Informalmente, tal regla afirma que cada cadena $w$ sobre $\mathrm{\Sigma }$ que satisface cada una de las condiciones sintácticas representadas por ${\alpha }_1$, ..., ${\alpha }_m$ y ninguna de las condiciones sintácticas representadas por ${\beta }_1$, ..., ${\beta }_n$ satisface la condición definida por $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 lenguajes de ecuaciones con uniones, intersecciones, complementos 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 de lenguaje, algunos se basan en ideas del campo de la programación lógica. Sin embargo, estos problemas 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 gramáticas libres de contexto, como los algoritmos de análisis eficientes, ver Plantilla:Harvtxt .

Referencias

• Plantilla:Cita publicación
• Okhotin, Alexander (2006). Nueve problemas abiertos sobre gramáticas conjuntivas y booleanas (PDF) (Informe técnico). TUCS 794.
• Plantilla:Cita publicación
• 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. Preprint disponible en línea.

Enlaces externos

• Página de Okhotin sobre gramáticas booleanas