Reescritura regulada

Definición de una gramática matricial,${\displaystyle MG}$, es una cuádrupla${\displaystyle G=(N,T,M,S)}$donde 1.-${\displaystyle N}$es un alfabeto de símbolos no terminales 2.-${\displaystyle T}$es un alfabeto de símbolos terminales disjuntos con${\displaystyle N}$ 3.-${\displaystyle M={m_{1},m_{2},...,m_{n}}}$es un conjunto finito de matrices, que son secuencias no vacías ${\displaystyle m_{i}=[p_{i_{1}},...,p_{i_{k(i)}}]}$, con${\displaystyle k(i)\geq 1}$, y ${\displaystyle 1\leq i\leq n}$, donde cada ${\displaystyle p_{i_{j}}1\leq j\leq k(i)}$es un par ordenado ${\ Displaystyle p_ {i_ {j}} = (L, R)}$ ser ${\displaystyle L\in (N\cup T)^{*}N(N\cup T)^{*},R\in (N\cup T)^{*}}$ Estos pares se denominan "producciones" y se denotan ${\displaystyle L\rightarrow R}$En estas condiciones, las matrices se pueden escribir como ${\displaystyle m_{i}=[L_{i_{1}}\rightarrow R_{i_{1}},...,L_{i_{k(i)}}\rightarrow R_{i_{k(i)}}]}$ 4.- La S es el símbolo de inicio

Definición Dejemos${\displaystyle MG=(N,T,M,S)}$sea ​​una gramática matricial y deje que${\displaystyle P}$ la colección de todas las producciones en matrices de${\displaystyle MG}$. Dijimos que${\displaystyle MG}$es de tipo${\displaystyle i}$según la jerarquía de Chomsky con${\displaystyle i=0,1,2,3}$o "longitud creciente" o "lineal" o "sin${\displaystyle \lambda }$-producciones" si y solo si la gramática${\displaystyle G=(N,T,P,S)}$tiene la propiedad correspondiente.

Nota: tomado de Abraham 1965, con cambio de nombres de no terminales.

El lenguaje sensible al contexto ${\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 1\}}$ es generado por el${\displaystyle CFMG}$${\displaystyle G=(N,T,M,S)}$dónde ${\displaystyle N=\{S,A,B,C\}}$es el conjunto no terminal, ${\displaystyle T=\{a,b,c\}}$es el conjunto terminal, y el conjunto de matrices se define como ${\displaystyle M:}$${\displaystyle \left[S\rightarrow abc\right]}$, ${\displaystyle \left[S\rightarrow aAbBcC\right]}$, ${\displaystyle \left[A\rightarrow aA,B\rightarrow bB,C\rightarrow cC\right]}$, ${\displaystyle \left[A\rightarrow a,B\rightarrow b,C\rightarrow c\right]}$.

Una gramática programada es un par${\displaystyle (G,s)}$dónde ${\displaystyle G=(N,T,P,S)}$ es una gramática y${\displaystyle s,f:P\rightarrow 2^{P}}$son las funciones de éxito y fracaso del conjunto de producciones a la clase de subconjuntos del conjunto de producciones.

Definición Una gramática con lenguaje de control regular , ${\displaystyle GWRCL}$, es un par${\displaystyle (G,e)}$dónde ${\displaystyle G=(N,T,P,S)}$ es una gramática y${\displaystyle e}$es una expresión regular sobre el alfabeto del conjunto de producciones.

Consideremos el CFG ${\displaystyle G=(N,T,P,S)}$dónde ${\displaystyle N=\{S,A,B,C\}}$es el conjunto no terminal, ${\displaystyle T=\{a,b,c\}}$es el conjunto terminal, y el conjunto de producciones se define como ${\displaystyle P=\{p_{0},p_{1},p_{2},p_{3},p_{4},p_{5},p_{6}\}}$ ser ${\displaystyle p_{0}=S\rightarrow ABC}$${\displaystyle p_{1}=A\rightarrow aA}$, ${\displaystyle p_{2}=B\rightarrow bB}$, ${\displaystyle p_{3}=C\rightarrow cC}$${\displaystyle p_{4}=A\rightarrow a}$, ${\displaystyle p_{5}=B\rightarrow b}$, y ${\displaystyle p_{6}=C\rightarrow c}$. Claramente, ${\displaystyle L(G)=\{a^{*}b^{*}c^{*}\}}$Ahora bien, considerando las producciones establecidas ${\displaystyle P}$como un alfabeto (ya que es un conjunto finito), defina la expresión regular sobre${\displaystyle P}$: ${\displaystyle e=p_{0}(p_{1}p_{2}p_{3})^{*}(p_{4}p_{5}p_{6})}$.

Combinando la gramática CFG${\displaystyle G}$y la expresión regular ${\displaystyle e}$, obtenemos el CFGWRCL ${\ Displaystyle (G, e) = (G, p_ {0} (p_ {1} p_ {2} p_ {3}) ^ {*} (p_ {4} p_ {5} p_ {6}}}}$ que genera el lenguaje ${\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 1\}}$.

Además de que existen otras gramáticas con reescritura regulada, las cuatro citadas anteriormente son buenos ejemplos de cómo extender las gramáticas libres de contexto con algún tipo de mecanismo de control para obtener un dispositivo gramatical potente, similar a una máquina de Turing .