Producción (informática)

Método de sustitución de símbolos

Una producción o regla de producción en informática es una regla de reescritura que especifica una sustitución de símbolo que se puede realizar de forma recursiva para generar nuevas secuencias de símbolos. Un conjunto finito de producciones es el componente principal en la especificación de una gramática formal (específicamente una gramática generativa ). Los otros componentes son un conjunto finito de símbolos no terminales , un conjunto finito (conocido como alfabeto) de símbolos terminales que es disjunto de y un símbolo distinguido que es el símbolo de inicio . ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle N}$ ${\displaystyle S\in N}$

En una gramática sin restricciones , una producción tiene la forma , donde y son cadenas arbitrarias de terminales y no terminales, y no pueden ser la cadena vacía . Si es la cadena vacía, esto se denota con el símbolo , o (en lugar de dejar el lado derecho en blanco). Por lo tanto, las producciones son miembros del producto cartesiano. ${\displaystyle u\to v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \epsilon }$ ${\displaystyle \lambda }$

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

donde es el vocabulario , es el operador de estrella de Kleene , indica concatenación , denota unión de conjuntos y denota conjunto menos o diferencia de conjuntos . Si no permitimos que el símbolo de inicio aparezca en (la palabra del lado derecho), tenemos que reemplazar por en el lado derecho del símbolo de producto cartesiano. ^[1] ${\displaystyle V:=N\cup \Sigma }$ ${\displaystyle {}^{*}}$ ${\displaystyle V^{*}NV^{*}}$ ${\displaystyle \cup }$ ${\displaystyle \setminus }$ ${\displaystyle v}$ ${\displaystyle V^{*}}$ ${\displaystyle (V\setminus \{S\})^{*}}$

Los otros tipos de gramática formal de 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 (N\cup \Sigma )^{*}}$

Generación de gramática

Para generar una cadena en el lenguaje, se comienza con una cadena que consta de un solo símbolo de inicio y luego se aplican sucesivamente las reglas (cualquier número de veces, en cualquier orden) para reescribir esta cadena. Esto se detiene 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 particular de elecciones legales tomadas durante este proceso de reescritura produce una cadena particular en el lenguaje. Si hay múltiples formas diferentes de generar esta única cadena, entonces se dice que la gramática es ambigua .

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

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

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

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

Véase también

• 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 frase
• Sistema postcanónico (Sistemas de producción de Emil Post: un modelo de computación).

Referencias

1. Véase Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronization von Halbspursprachen Archivado el 17 de enero de 2018 en Wayback Machine ; Fakultät Informatik der Universität Stuttgart; 1994 (alemán)