Gramática matricial

Una gramática matricial es una gramática formal en la que en lugar de producciones individuales, las producciones se agrupan en secuencias finitas. Una producción no puede aplicarse por separado, debe aplicarse en secuencia. En la aplicación de dicha secuencia de producciones, la reescritura se realiza de acuerdo con cada producción en secuencia, la primera, la segunda, etc. hasta que la última producción se haya utilizado para la reescritura. Las secuencias se conocen como matrices.

La gramática matricial es una extensión de la gramática libre de contexto y una instancia de una gramática controlada.

Definición formal

Una gramática matricial es un cuádruplo ordenado

Dónde

• $V_{N}$ es un conjunto finito de no terminales
• $V_{T}$ es un conjunto finito de terminales
• $X_{0}$ es un elemento especial de $V_{N}$, viz. el símbolo inicial
• $M$ es un conjunto finito de secuencias no vacías cuyos elementos son pares ordenados

$(P,Q),\quad P\in W(V)V_{N}W(V),\quad Q\in W(V),\quad V=V_{N}\cup V_{T}.$

Los pares se llaman producciones, escritas como .  Las secuencias se llaman matrices y se pueden escribir como

Sea $F$ el conjunto de todas las producciones que aparecen en las matrices $m$ de una gramática matricial $G$. Entonces la gramática matricial $G$ es de tipo-$i,i=0,1,2,3$, longitud creciente, lineal, $\lambda$-free, libre del contexto o sensible al contexto si y solo si la gramática $G_{1}=(V_{N},V_{T},X_{0},F)$ tiene la siguiente propiedad.

Para una gramática matricial $G$, una relación binaria $\Rightarrow _{G}$ es definida; también representado como $\Rightarrow$. Para cualquier $P,Q\in W(V)$, $P\Rightarrow Q$ contiene si y solo si existe un número entero $r\geq 1$ de tal manera que las palabras

$\alpha _{1},,\ldots ,\alpha _{r+1},\quad P_{1},\ldots ,P_{r},\quad R_{1},\ldots ,R_{r},\quad ,R^{1},\ldots ,R^{r}$

sobre V existen y

• $\alpha _{i}=P$ y $\alpha _{r+1}=Q$
• $m$ es una de las matrices de $G$
• $\alpha _{i}=R_{i}P_{i}R^{i}$ y $\alpha _{i+1}=R_{i}Q_{i}R^{i}.$

Si se cumplen las condiciones anteriores, también se dice que $P\Rightarrow Q$ sostiene con $(m,R_{1})$ como las especificaciones .

Sea $\Rightarrow ^{*}$ el cierre transitivo reflexivo de la relación $\Rightarrow$. Entonces, el lenguaje generado por la gramática de la matriz $G$ viene dado por:

$L(G)=\{P\in W(V_{T})|X_{0}\Rightarrow ^{*}P\}.$

Ejemplo

Considerar la gramática matricial

$G=(\{S,X,Y\},\{a,b,c\},S,M)$

donde $M$ es una colección que contiene las siguientes matrices:

$[S\rightarrow XY],\quad [X\rightarrow aXb,Y\rightarrow cY],\quad [X\rightarrow ab,Y\rightarrow c]$

Estas matrices, que contienen solo reglas "libres del contexto" generan el lenguaje "sensible al contexto"

$L=\{a^{n}b^{n}c^{n}|n\geq 1\}.$

Propiedades

Sea ${\ce {MAT^{\lambda }}}$ la clase de lenguajes producidos por gramáticas matriciales, y MAT la clase de lenguajes producidos por $\lambda$-free gramáticas matriciales.

• Trivialmente, MAT está incluido en ${\ce {MAT^{\lambda }}}$.
• Todos los lenguajes libres del contexto están en MAT,y todos los lenguajes en ${\ce {MAT^{\lambda }}}$ son recursivamente enumerable.
• MAT está cerrado debajo unión, concatenatión, intersectión con lenguajes regulares y permutación.
• Todos los lenguajes en MAT puede ser producido por un gramática sensible al contexto.
• Existe un lenguaje sensible al contexto que no pertenece a ${\ce {MAT^{\lambda }}}$ .
• Cada lenguaje producido por una gramática matricial con un solo símbolo de terminal es regular.

Problemas abiertos

No se sabe si existen lenguajes en ${\ce {MAT^{\lambda }}}$ que no están en MAT, y tampoco se sabe si ${\ce {MAT^{\lambda }}}$ contiene lenguajes que no son contextuales.

• Datos: Q48789625