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 conectivo lógico expresable en gramáticas libres de 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 .

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 cada cadena sobre que satisface cada una de las condiciones sintácticas representadas por , ..., por lo tanto satisface 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}$

Definición formal

Una gramática conjuntiva se define mediante la tupla de 4 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 u oración. Las variables también se denominan a veces categorías sintácticas. ${\displaystyle v\in V}$
2. Σ es un conjunto finito de terminales s, disjuntos de V , que forman el contenido real de la oración. El conjunto de terminales es el alfabeto de la lengua definido por la gramática G .
3. R es un conjunto finito de producciones, cada una de las cuales tiene la forma para algunas 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 la oración completa (o el 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. Las reglas y, por lo tanto, 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 definición se basa en representar la gramática como un sistema de ecuaciones lingüísticas con unión, intersección y concatenación y considerar su solución mínima. La otra definición generaliza la definición generativa de Chomsky de las gramáticas independientes del contexto utilizando la reescritura de términos sobre conjunción y concatenación.

Definición por derivació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\Rightarrow 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 , escrito como , si 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 que genera. ${\displaystyle G=(V,\Sigma ,R,S)}$

Ejemplo

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, como lo demuestra el lema de bombeo para lenguajes libres de contexto . ${\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 0\}}$

Algoritmos de análisis

Aunque el poder expresivo de las gramáticas conjuntivas es mayor que el de las gramáticas libres de contexto, las gramáticas conjuntivas conservan algo de lo último. Lo más importante es que existen generalizaciones de los principales algoritmos de análisis sintáctico libres de contexto, incluidos el descenso recursivo en tiempo lineal, el LR generalizado en tiempo cúbico , el algoritmo Cocke-Kasami-Younger en tiempo cúbico , así como el algoritmo de Valiant que se ejecuta tan rápido como la multiplicación de matrices.

Propiedades teóricas

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

La familia de lenguajes conjuntivos está 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 son problemas aún abiertos (a fecha de 2001). ^{[1] : 533}

Se ha investigado el poder expresivo de las gramáticas sobre un alfabeto de una sola letra. ^{[ cita requerida ]}

Este trabajo proporcionó una base para el estudio de ecuaciones lingüísticas de una forma más general.

Autómatas de empuje alternado sincronizado

Aizikowitz y Kaminski ^[2] introdujeron una nueva clase de autómatas de empuje (PDA) llamada autómatas de empuje alternados sincronizados (SAPDA). Demostraron que eran equivalentes a las gramáticas conjuntivas de la misma manera que los PDA no deterministas son equivalentes a las gramáticas libres de contexto.

Notas

1. Dada una gramática conjuntiva, ¿su lenguaje generado es vacío / finito / regular / libre de contexto?
2. Dadas dos gramáticas conjuntivas, ¿el lenguaje generado por la primera es un subconjunto de / igual al de la segunda?

Referencias

1. Alexander Okhotin (2001). "Gramáticas conjuntivas" (PDF) . Revista de autómatas, lenguajes y combinatoria . 6 (4): 519–535.
2. Aizikowitz, Tamar; Kaminski, Michael (2011). "Gramáticas conjuntivas LR(0) y autómatas de empuje alternado sincronizado determinista". Ciencias de la computación: teoría y aplicaciones . Apuntes de clase en ciencias de la computación. Vol. 6651. págs. 345–358. doi :10.1007/978-3-642-20712-9_27. ISBN 978-3-642-20711-2. ISSN  0302-9743.

Enlaces externos

• Artur Jeż (2007). "Las gramáticas conjuntivas generan lenguajes unarios no regulares" (PDF) (Diapositivas de la conferencia celebrada en la Conferencia Internacional sobre Desarrollos en la Teoría del Lenguaje ) . Consultado el 5 de noviembre de 2019 .
• «Página de Alexander Okhotin sobre gramáticas conjuntivas». 9 de octubre de 2011. Consultado el 5 de noviembre de 2019 .
• Alexander Okhotin (2007). "Nueve problemas abiertos para gramáticas conjuntivas y booleanas". Boletín de la EATCS . ​​Archivado desde el original el 29 de septiembre de 2007.
• Alexander Okhotin (2013). "Gramáticas conjuntivas y booleanas: el verdadero caso general de las gramáticas libres de contexto". Computer Science Review . 9 : 27–59. doi :10.1016/j.cosrev.2013.06.001. Este artículo reemplaza los estudios anteriores, "Una visión general de las gramáticas conjuntivas" (Boletín de la EATCS, 2004) y "Nueve problemas abiertos para las gramáticas conjuntivas y booleanas".
• Jeż, Artur (2008). "Las gramáticas conjuntivas generan lenguajes unarios no regulares". Revista Internacional de Fundamentos de la Ciencia de la Computación . 19 (3): 597–615. doi :10.1142/S012905410800584X.Versión del informe técnico (pdf) ^{[ enlace muerto permanente ]}