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

editar

Una gramática matricial es un cuádruplo ordenado

Dónde

  •   es un conjunto finito de no terminales
  •   es un conjunto finito de terminales
  •   es un elemento especial de  , viz. el símbolo inicial
  •   es un conjunto finito de secuencias no vacías cuyos elementos son pares ordenados
 

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

Sea   el conjunto de todas las producciones que aparecen en las matrices   de una gramática matricial  . Entonces la gramática matricial   es de tipo- , longitud creciente, lineal,  -free, libre del contexto o sensible al contexto si y solo si la gramática   tiene la siguiente propiedad.

Para una gramática matricial  , una relación binaria   es definida; también representado como  . Para cualquier  ,   contiene si y solo si existe un número entero   de tal manera que las palabras

 

sobre V existen y

  •   y  
  •   es una de las matrices de  
  •   y  

Si se cumplen las condiciones anteriores, también se dice que   sostiene con   como las especificaciones .

Sea   el cierre transitivo reflexivo de la relación  . Entonces, el lenguaje generado por la gramática de la matriz   viene dado por:

 

Ejemplo

editar

Considerar la gramática matricial

 

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

 

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

 

Propiedades

editar

Sea   la clase de lenguajes producidos por gramáticas matriciales, y MAT la clase de lenguajes producidos por  -free gramáticas matriciales.

  • Trivialmente, MAT está incluido en  .
  • Todos los lenguajes libres del contexto están en MAT,y todos los lenguajes en   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   .
  • Cada lenguaje producido por una gramática matricial con un solo símbolo de terminal es regular.

Problemas abiertos

editar

No se sabe si existen lenguajes en   que no están en MAT, y tampoco se sabe si   contiene lenguajes que no son contextuales.