Gramática matricial

Uma gramática matricial é uma gramática formal na qual ao invés de produções individuais, as produções são agrupadas em sequências finitas. Uma produção não pode ser aplicada separadamente, devendo ser aplicada em sequência. Na aplicação de uma sequência de produções, a reescrita é feita de acordo com cada produção em sequência: primeira produção, segunda e assim por diante até que a última produção seja utilizada para reescrita. A sequência é referenciada como matrizes.

Gramática matricial é uma extensão de gramática livre de contexto, e uma instância de gramáticas controladas.

Definição formal

Uma gramática matricial é uma 4-upla ordenada

$G=(V_{N},V_{T},X_{0},M).$

onde

• $V_{N}$ é o conjunto finito de não-terminais
• $V_{T}$ é o conjunto finito de terminais
• $X_{0}$ é um elemento especial de $V_{N}$, também chamado de símbolo inicial
• $M$ é o conjunto finito de sequências não vazias cujo elementos são 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}.$

Os pares são chamados de produções, escritas como $P\to Q$. As sequências são chamadas de matrizes e podem ser escritas como

$m=[P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}].$

Seja $F$ o conjunto de todas as produções que aparece nas matrizes $m$ de uma gramática $G$. Então, a gramática matricial $G$ é do tipo-$i,i=0,1,2,3$, comprimento crescente, linear, $\lambda$-livre, livre de contexto ou sensível ao contexto se e somente se a gramática $G_{1}=(V_{N},V_{T},X_{0},F)$ tem a seguinte propriedade.

Para uma gramática matricial $G$, uma relação binária $\Rightarrow _{G}$ é definida; também representada como $\Rightarrow$. Para qualquer $P,Q\in W(V)$, $P\Rightarrow Q$ é verdade se e somente se existir um inteiro $r\geq 1$ tal que as palavras

$\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 existam e

• $\alpha _{i}=P$ e $\alpha _{r+1}=Q$
• $m$ é uma das matrizes de $G$
• $\alpha _{i}=R_{i}P_{i}R^{i}$ e $\alpha _{i+1}=R_{i}Q_{i}R^{i}.$

Se as condições acima são satisfeitas, então também pode-se dizer que $P\Rightarrow Q$ é verdade com $(m,R_{1})$ seguindo as especificações.

Seja $\Rightarrow ^{*}$ um fechamento transitivo reflexivo de uma relação $\Rightarrow$. Então, a linguagem gerada pela gramática matricial $G$ é dada por

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

Exemplo

Considere a gramática matricial

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

onde $M$ é uma coleção contendo as seguintes matrizes:

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

Essas matrizes, as quais contém apenas regras livres de contexto, geram a linguagem sensível a contexto

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

Este exemplo pode ser encontrado nas páginas 8 e 9 de .

Propriedades

Seja $MAT^{\lambda }$ a classe das linguagens produzidas pelas gramáticas matriciais, e $MAT$ a classe das linguagens produzidas por gramáticas matriciais $\lambda$-livres.

• Trivialmente, $MAT$ está incluso em $MAT^{\lambda }$.
• Todas gramáticas livre de contexto estão em $MAT$, e todas as linguagens em $MAT^{\lambda }$ são recursivamente enumeráveis.
• $MAT$ é fechada sob união, concatenação, interseção com linguagens regulares e permutação.
• Todas as linguagens em $MAT$ podem ser produzidas por uma gramática sensível ao contexto.
• Existe uma linguagem sensível ao contexto que não pertence a $MAT^{\lambda }$ .
• Cada linguagem produzida por uma gramática com apenas um símbolo terminal é regular.

Problemas em aberto

Não se sabe existem linguagens que estão em $MAT^{\lambda }$ mas que não estão em $MAT$, e também não se sabe se $MAT^{\lambda }$ contém linguagens que não são sensíveis ao contexto .

Referências

• ↑ Ábrahám, S. Some questions of language theory. International Conference on Computational Linguistic, 1965. pp 1-11. [4]
• ↑ Gheorghe Păun, Membrane Computing: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. pp 30-32