Producción (informática)

En informática , una producción o regla de producción es una regla de reescritura que reemplaza algunos símbolos con otros símbolos. ^{[ 1 ]} Un conjunto finito de producciones${\displaystyle P}$es el componente principal en la especificación de una gramática formal (específicamente una gramática generativa ).

En dichas gramáticas, un conjunto de producciones es un caso especial de relación en el conjunto de cadenas.${\displaystyle V^{*}}$(dónde${\displaystyle {}^{*}}$es el operador estrella de Kleene ) sobre un conjunto finito de símbolos${\displaystyle V}$llamado vocabulario que define qué cadenas no vacías pueden sustituirse por otras. El conjunto de producciones es, por lo tanto, un subconjunto de tipo especial.

${\displaystyle P\subconjunto V^{*}\times V^{*}}$

y las producciones se escriben luego en la forma${\displaystyle u\to v}$para significar que${\displaystyle (u,v)\in P}$(no confundir con${\displaystyle \to }$se utiliza como notación de función, ya que puede haber múltiples reglas para la misma.${\displaystyle u}$). Dados dos subconjuntos${\displaystyle A,B\subset V^{*}}$Las producciones pueden estar restringidas para satisfacer${\displaystyle P\subset A\times B}$, en cuyo caso se dice que las producciones "son de la forma${\displaystyle A\to B}$. Diferentes opciones y construcciones de${\displaystyle A,B}$conducen a diferentes tipos de gramáticas. En general, cualquier producción de la forma

${\displaystyle u\to \epsilon ,}$

dónde${\displaystyle \epsilon }$es la cadena vacía (a veces también se denota${\displaystyle \lambda }$), se denomina regla de borrado , mientras que las producciones que generarían cadenas de la nada, es decir, de la forma

${\displaystyle \epsilon \to v,}$

Nunca están permitidos.

Para permitir que las reglas de producción creen oraciones significativas, el vocabulario se divide en conjuntos ( disjuntos ).${\displaystyle \Sigma }$y${\displaystyle N}$desempeñando dos funciones diferentes:

• ${\displaystyle \Sigma }$denota los símbolos terminales conocidos como un alfabeto que contiene los símbolos permitidos en una oración;
• ${\displaystyle N}$denota símbolos no terminales , que contienen un símbolo de inicio distinguido${\displaystyle S\in N}$, que son necesarias junto con las reglas de producción para definir cómo construir las oraciones.

En el caso más general de una gramática no restringida , una producción${\displaystyle u\to v}$, se permite mapear cadenas arbitrarias${\displaystyle u}$y${\displaystyle v}$en${\displaystyle V}$(terminales y no terminales), siempre que${\displaystyle u}$no está vacío. Por lo tanto, las gramáticas no restringidas tienen producciones de la forma

${\displaystyle V^{*}\setminus \{\epsilon \}\to V^{*}}$

o si queremos impedir que se modifiquen las oraciones terminadas

${\displaystyle V^{*}NV^{*}=(V^{*}\setminus \Sigma ^{*})\to V^{*}}$,

dónde${\displaystyle V^{*}NV^{*}}$indica concatenación y obliga a que un símbolo no terminal esté siempre presente en el lado izquierdo de las producciones, y${\displaystyle \setminus }$denota conjunto menos o conjunto diferencia . Si no permitimos que aparezca el símbolo de inicio en${\displaystyle v}$(la palabra del lado derecho), tenemos que reemplazar${\displaystyle V^{*}}$con${\displaystyle (V\setminus \{S\})^{*}}$en el lado derecho. ^{[ 2 ]}

Los otros tipos de gramática formal en la jerarquía de Chomsky imponen restricciones adicionales sobre lo que constituye una producción. En particular, en una gramática libre de contexto , el lado izquierdo de una producción debe ser un único símbolo no terminal. Por lo tanto, las producciones tienen la forma:

${\displaystyle N\to V^{*}}$

Para generar una cadena en este lenguaje, se parte de una cadena que consta de un único símbolo inicial y, a continuación, se aplican sucesivamente las reglas (cualquier número de veces y en cualquier orden) para reescribirla. Este proceso finaliza cuando se obtiene una cadena que contiene solo terminales. El lenguaje consta de todas las cadenas que se pueden generar de esta manera. Cualquier secuencia de elecciones válidas durante este proceso de reescritura produce una cadena específica en el lenguaje. Si existen varias formas diferentes de generar esta única cadena, se dice que la gramática es ambigua .

Por ejemplo, supongamos que el alfabeto consta de${\displaystyle a}$y${\displaystyle b}$, con el símbolo de inicio${\displaystyle S}$y tenemos las siguientes reglas:

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ba}$

entonces comenzamos con${\displaystyle S}$y puede elegir una regla para aplicarle. Si elegimos la regla 1, reemplazamos${\displaystyle S}$con${\displaystyle aSb}$y obtener la cadena${\displaystyle aSb}$. Si volvemos a elegir la regla 1, reemplazamos${\displaystyle S}$con${\displaystyle aSb}$y obtener la cadena${\displaystyle aaSbb}$. Este proceso se repite hasta que solo tengamos símbolos del alfabeto (es decir,${\displaystyle a}$y${\displaystyle b}$). Si ahora elegimos la regla 2, reemplazamos${\displaystyle S}$con${\displaystyle ba}$y obtener la cadena${\displaystyle aababb}$y ya están hechas. Podemos escribir esta serie de elecciones de forma más breve, usando símbolos:${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$El lenguaje de la gramática es el conjunto de todas las cadenas que se pueden generar utilizando este proceso:${\displaystyle \{ba,abab,aababb,aaababbb,\dotsc \}}$.

• Gramática formal
• Autómatas finitos
• gramática generativa
• Sistema L
• Regla de reescritura
• Forma Backus-Naur (Una forma compacta para escribir las producciones de una gramática libre de contexto).
• Regla de estructura de frases
• Sistema postcanónico (sistemas de producción de Emil Post: un modelo de computación).