Producción (informática)

Método de sustitución de símbolos.

Una regla de producción o producción en informática es una regla de reescritura que especifica una sustitución de símbolos 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 y un símbolo distinguido que es el símbolo inicial . ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle N}$ ${\displaystyle S\in N}$

En una gramática no restringida , una producción tiene la forma donde y son cadenas arbitrarias de terminales y no terminales, y no puede ser la cadena vacía . Si es una cadena vacía, esto se indica con el símbolo o (en lugar de dejar el lado derecho en blanco). Entonces 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 está el vocabulario , es el operador estrella de Kleene , indica concatenación , denota unión de conjuntos y denota conjunto menos o diferencia de conjuntos . Si no permitimos que aparezca el símbolo de inicio en (la palabra del lado derecho), tenemos que reemplazarlo por en el lado derecho del símbolo del 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 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. Entonces las producciones son de 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 inicial 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 varias 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}$

luego comenzamos con y podemos elegir una regla para aplicarle. Si elegimos la regla 1, reemplazamos por y obtenemos la cadena . Si volvemos a elegir la regla 1, reemplazamos por 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 forma más breve, utilizando símbolos: . El lenguaje de la gramática es el conjunto de todas las cadenas que se pueden generar mediante 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 \}}$

Ver también

• Gramática formal
• autómatas finitos
• Gramática generativa
• sistema L
• Reescribir regla
• Forma Backus-Naur (una forma compacta para escribir las producciones de una gramática libre de contexto).
• Regla de estructura de frase
• Sistema poscanó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)