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 único símbolo no terminal, que es el único conector lógico expresable en las gramáticas libres de contexto. La conjunción puede utilizarse, en particular, para especificar la intersección de lenguajes. Una extensión adicional de las gramáticas conjuntivas, conocida como gramática booleana, permite además la negación explícita .

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

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

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

Una gramática conjuntiva se define por la cuádrupla donde ${\displaystyle G}$${\displaystyle G=(V,\Sigma,R,S)}$

1. V es un conjunto finito ; cada elemento se denomina símbolo no terminal o variable . Cada variable representa un tipo diferente de frase o cláusula en la oración. A las variables también se las denomina a veces categorías sintácticas.${\displaystyle v\in V}$
2. Σ es un conjunto finito de terminales s , disjunto de V , que conforman el contenido real de la oración. El conjunto de terminales es el alfabeto del lenguaje definido por la gramática G.
3. R es un conjunto finito de producciones, cada una de la forma para algún en y . Los miembros de R se denominan reglas o producciones de la gramática.${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}$${\displaystyle A}$${\displaystyle V}$${\displaystyle \alpha _{i}\in (V\cup \Sigma )^{*}}$
4. S es la variable de inicio (o símbolo de inicio), que se utiliza para representar toda la frase ( o programa). Debe ser un elemento de V.

Es común enumerar todos los lados derechos del mismo lado izquierdo en la misma línea, usando | (el símbolo de barra vertical ) para separarlos. Por lo tanto, las reglas y se pueden escribir como . ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}$${\displaystyle A\rightarrow \beta _{1}\&\ldots \&\beta _{n}}$${\displaystyle 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 se basa en representar la gramática como un sistema de ecuaciones lingüísticas con unión, intersección y concatenación, considerando su solución mínima. La otra generaliza la definición generativa de Chomsky para las gramáticas libres de contexto mediante la reescritura de términos sobre conjunción y concatenación.

Para cualquier cadena , decimos que u produce directamente v , escrito como , si ${\displaystyle u,v\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$${\displaystyle u\Flecha derecha v\,}$

• o bien existe una regla tal que y ,${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\in R}$${\displaystyle u\,=u_{1}Au_{2}}$${\displaystyle v\,=u_{1}(\alpha _{1}\&\ldots \&\alpha _{m})u_{2}}$
• o existe una cadena tal que y .${\displaystyle w\in (V\cup \Sigma )^{*}}$${\displaystyle u\,=u_{1}(w\&\ldots \&w)u_{2}}$${\displaystyle v\,=u_{1}wu_{2}}$

Para cualquier cadena decimos que G genera w , escrita como , si es tal que . ${\displaystyle w\in \Sigma ^{*},}$${\displaystyle S\ {\stackrel {*}{\Rightarrow }}\ w}$${\displaystyle \exists k\geq 1\,\exists \,u_{1},\cdots ,u_{k}\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$${\displaystyle S=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=w}$

El lenguaje de una gramática es el conjunto de todas las cadenas de caracteres que genera. ${\displaystyle G=(V,\Sigma,R,S)}$

La gramática , con producciones ${\displaystyle G=(\{S,A,B,C,D\},\{a,b,c\},R,S)}$

${\displaystyle S\rightarrow AB\&DC}$,

${\displaystyle A\rightarrow aA\ |\ \epsilon }$,

${\displaystyle B\rightarrow bBc\ |\ \epsilon }$,

${\displaystyle C\rightarrow cC\ |\ \epsilon }$,

${\displaystyle D\rightarrow aDb\ |\ \epsilon }$,

es conjuntivo. Una derivación típica es

${\displaystyle S\Rightarrow (AB\&DC)\Rightarrow (aAB\&DC)\Rightarrow (aB\&DC)\Rightarrow (abBc\&DC)\Rightarrow (abc\&DC)\Rightarrow (abc\&aDbC)\Rightarrow (abc\&abC)\Rightarrow (abc\&abcC)\Rightarrow (abc\&abc)\Rightarrow abc}$

Se puede demostrar que . El lenguaje no es libre de contexto, probado por el lema de bombeo para lenguajes libres de contexto . ${\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 0\}}$

Si bien el poder expresivo de las gramáticas conjuntivas es mayor que el de las gramáticas libres de contexto, las gramáticas conjuntivas conservan algunas de las ventajas de estas últimas. Lo más importante es que existen generalizaciones de los principales algoritmos de análisis sintáctico libre de contexto, incluyendo el descenso recursivo de tiempo lineal, el LR generalizado de tiempo cúbico , el algoritmo de Cocke-Kasami-Younger de tiempo cúbico , así como el algoritmo de Valiant, que se ejecuta tan rápido como una multiplicación de matrices.

Una propiedad que ya es indecidible para lenguajes libres de contexto o intersecciones finitas de ellos, debe ser también indecidible para gramáticas conjuntivas; estas incluyen: vacuidad , finitud , regularidad , ausencia de contexto , ^{[ n 1 ]} inclusión y equivalencia. ^{[ n 2 ]}

La familia de lenguajes conjuntivos es cerrada bajo unión, intersección, concatenación y estrella de Kleene , pero no bajo homomorfismo de cadenas , prefijo , sufijo y subcadena . El cierre bajo complemento y bajo homomorfismo de cadenas libre de ε sigue siendo un problema abierto (a fecha de 2001). ^{[ 1 ] : 533}

Se ha investigado el poder expresivo de las gramáticas sobre un alfabeto de una sola letra.

Este trabajo sentó las bases para el estudio de ecuaciones lingüísticas de forma más general.

Aizikowitz and Kaminski^[2] introduced a new class of pushdown automata (PDA) called synchronized alternating pushdown automata (SAPDA). They proved it to be equivalent to conjunctive grammars in the same way as nondeterministic PDAs are equivalent to context-free grammars.

• Artur Jeż (2007). "Conjunctive grammars generate non-regular unary languages"(PDF) (Slides of talk held at the International Conference on Developments in Language Theory). Retrieved 5 November 2019.
• "Alexander Okhotin's page on conjunctive grammars". 9 October 2011. Retrieved 5 November 2019.
• Alexander Okhotin (2007). "Nine open problems for conjunctive and Boolean grammars". Bulletin of the EATCS. Archived from the original on 2007-09-29.
• Alexander Okhotin (2013). "Conjunctive and Boolean grammars: The true general case of the context-free grammars". Computer Science Review. 9: 27–59. doi:10.1016/j.cosrev.2013.06.001. This paper supersedes the earlier surveys, "An overview of conjunctive grammars" (Bulletin of the EATCS, 2004) and "Nine open problems for conjunctive and Boolean grammars"
• Jeż, Artur (2008). "Conjunctive grammars generate non-regular unary languages". International Journal of Foundations of Computer Science. 19 (3): 597–615. doi:10.1142/S012905410800584X.Versión del informe técnico (pdf)