Gramática matricial

Una gramática matricial es una gramática formal en la que las reglas de inferencia se agrupan en secuencias finitas. Las reglas de inferencia no se pueden aplicar individualmente, sino solo en secuencia. Al aplicar esta secuencia, la sustitución se realiza de acuerdo con cada regla de la secuencia, de la primera a la última. Las sucesiones se llaman matrices . La gramática matricial es una extensión de la gramática libre de contexto .

Formal definición

La gramática matricial es un quad ordenado

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

dónde

$V_{N}$ es un conjunto finito de símbolos no terminales
$VERMONT}$ es un conjunto finito de símbolos terminales
${\ estilo de visualización X_ {0} \ en V_ {N}}$ - símbolo de inicio
$METRO$ es un conjunto finito de secuencias no vacías de 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 denominan reglas de inferencia y se escriben como . Las sucesiones se llaman matrices y se escriben como ${\ estilo de visualización P \ a Q}$

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

Sea el conjunto de todas las reglas de inferencia en las matrices de la gramática matricial . Entonces, una gramática es una gramática de tipo , no abreviada , lineal , libre , libre de contexto o sensible al contexto si y solo si la gramática tiene esta propiedad. $F$ $metro$ $GRAMO$ $GRAMO$ ${\ estilo de visualización i, i = 0,1,2,3}$ $\lambda$ $G_{1}=(V_{N},V_{T},X_{0},F)$

Para una gramática matricial , se define una relación binaria , también denotada por . Para any , se cumple si y solo si hay un número entero tal que hay palabras $GRAMO$ ${\ estilo de visualización \ flecha derecha _ {G}}$ $\Flecha correcta$ ${\ estilo de visualización P, Q \ en W (V)}$ ${\ estilo de visualización P \ flecha derecha Q}$ $r\geq 1$

\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 el conjunto V y

${\ estilo de visualización \ alfa _ {i} = P}$ y ${\ estilo de visualización \ alfa _ {r + 1} = Q}$
${\ estilo de visualización m \ en G}$
${\ estilo de visualización \ alfa _ {i} = R_ {i} P_ {i} R ^ {i}}$ y $\alpha _{i+1}=R_{i}Q_{i}R^{i}.$

Si se cumplen las condiciones especificadas, también se dice que se cumple con la especificación . ${\ estilo de visualización P \ flecha derecha Q}$ ${\ estilo de visualización (m, R_ {1})}$

Sea una clausura transitiva reflexiva de la relación . Entonces, el lenguaje generado por la gramática matricial se define de la siguiente manera: ${\ estilo de visualización \ flecha derecha ^ {*}}$ $\Flecha correcta$ $GRAMO$

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

Ejemplo

Considere la gramática matricial

$G=(\{S,A,B\},\{a,b,c\},S,M)$

donde es la totalidad de las siguientes matrices: $METRO$

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

Estas matrices, que contienen solo reglas independientes del contexto , dan lugar a un lenguaje sensible al contexto.

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

Este ejemplo se puede encontrar en las páginas 8 y 9 [1] .

Notas

↑ Ábrahám, S. Algunas cuestiones de teoría del lenguaje. Conferencia Internacional sobre Lingüística Computacional, 1965. pp 1–11. [2] (enlace no disponible desde el 13-05-2013 [3454 días] - historial )