gramática conjuntiva

Las gramáticas conjuntivas 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 una operación de conjunción . Además de la conjunción explícita, las gramáticas conjuntivas 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 independientes del contexto. La conjunción se puede utilizar, en particular, para especificar la intersección de idiomas. Una extensión adicional de las gramáticas conjuntivas conocidas como gramáticas booleanas permite además la negación explícita .

donde es un no terminal y , ..., son cadenas formadas por símbolos en y (conjuntos finitos de símbolos terminales y no terminales respectivamente). Informalmente, tal regla afirma que cada cadena sobre eso satisface cada una de las condiciones sintácticas representadas por , ..., por lo tanto satisface la condición definida por . ${\ estilo de visualización A}$ ${\ estilo de visualización \ alfa _ {1}}$ ${\ estilo de visualización \ alfa _ {m}}$ ${\ estilo de visualización \ Sigma}$ ${\ estilo de visualización V}$ ${\ estilo de visualización w}$ ${\ estilo de visualización \ Sigma}$ ${\ estilo de visualización \ alfa _ {1}}$ ${\ estilo de visualización \ alfa _ {m}}$ ${\ estilo de visualización A}$

Una gramática conjuntiva se define por la tupla 4- donde ${\ estilo de visualización G}$ ${\ estilo de visualización G = (V, \ Sigma, R, S)}$

Es común listar todos los lados derechos para el mismo lado izquierdo en la misma línea, usando | (el símbolo de la tubería ) para separarlos. Reglas y , por lo tanto, puede escribirse como . $A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}$ $A\rightarrow \beta _{1}\&\ldots \&\beta _{n}$ $A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\ |\ \beta _{1}\&\ldots \&\beta _{n}$

Existen dos definiciones formales equivalentes del lenguaje especificado por una gramática conjuntiva. Una definición se basa en representar la gramática como un sistema de ecuaciones del lenguaje con unión, intersección y concatenación y considerando su solución mínima. La otra definición generaliza la definición generativa de Chomsky de las gramáticas libres de contexto utilizando la reescritura de términos sobre conjunción y concatenación.