Producción (informática)

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 un alfabeto) de símbolos terminales que es disjunta 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 puede ser la cadena vacía . Si es la cadena vacía, 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}$

donde es 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 el símbolo de inicio aparezca en (la palabra en el lado derecho), debemos reemplazar 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 solo símbolo no terminal. Entonces las producciones son de la forma:

Para generar una cadena en el idioma, 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 y en cualquier orden) para reescribir esta cadena. Esto se detiene cuando obtenemos 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 idioma. Si hay varias formas diferentes de generar esta única cadena, se dice que la gramática es ambigua .