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 produccioneses el componente principal en la especificación de una gramática formal (específicamente una gramática generativa ). Los otros componentes son un conjunto finitode símbolos no terminales , un conjunto finito (conocido como alfabeto)de símbolos terminales que es disjunto de y un símbolo distinguido ese es el símbolo de inicio .
En una gramática irrestricta , una producción tiene la forma, dónde y son cadenas arbitrarias de terminales y no terminales, y puede que no sea 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). Entonces las producciones son miembros del producto cartesiano
- ,
dónde es el vocabulario ,es el operador estrella de Kleene ,indica concatenación ,denota unión de conjuntos , ydenota un conjunto menos o una diferencia de conjunto . Si no permitimos que aparezca el símbolo de inicio en (la palabra en el lado derecho), tenemos que reemplazar por en el lado derecho del símbolo del producto cartesiano. [1]
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:
Generación de gramática
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, 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 .
Por ejemplo, suponga que el alfabeto consta de y , con el símbolo de inicio , y tenemos las siguientes reglas:
- 1.
- 2.
entonces comenzamos con y puede elegir una regla para aplicarle. Si elegimos la regla 1, reemplazamos con y obtener la cadena . Si elegimos la regla 1 nuevamente, reemplazamos con y obtener la cadena . Este proceso se repite hasta que solo tenemos símbolos del alfabeto (es decir, y ). Si ahora elegimos la regla 2, reemplazamos con y obtener la cadena y listo. Podemos escribir esta serie de opciones más brevemente, usando símbolos:. El lenguaje de la gramática es el conjunto de todas las cadenas que se pueden generar mediante este proceso:.
Ver también
- Gramática formal
- Autómatas finitos
- Gramática generativa
- Sistema L
- Reescribir la 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 cálculo).
Referencias
- ^ Ver Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronization von Halbspursprachen Archivado el 17 de enero de 2018 en la Wayback Machine ; Fakultät Informatik der Universität Stuttgart; 1994 (alemán)