Producciones y Derivaciones

Definimos algunas notaciones para describir reglas de sustitución, es decir, como derivar una palabra con las producciones de la gramática:

Una producción $p$ es una tupla de un conjunto cartesiano sobre dos universos (que pueden ser el mismo), es decir, $p=(A,B)\in\mbox{$\Sigma^*$}_1\times\mbox{$\Sigma^*$}_2$.

Sea $(A,B)$ una producción, en vez de tuplas también escribimos: $A\longrightarrow B$.

Un conjunto de producciones se llama sistema de producciones (o sistema de reglas). A este nivel todavía no decimos mucho sobre los alfabetos involucrados, más adelante concretaremos.

Una derivación directa $v\longrightarrow w$ es una conversión de una palabra en otra aplicando una producción, es decir, sea por ejemplo $v=aAb$ una palabra, y sea $A\longrightarrow B$ una producción, entonces se puede derivar la palabra $w=aBb$ directamente desde $v$ sustituyendo la subpalabra $A$ por la palabra $B$ como indica la producción.

Ejemplo: Sean $000\longrightarrow 010$ y $10\longrightarrow 01$ dos producciones. Desde $v=1000$ se puede derivar $w_1=1010$ aplicando la primera producción, y $w_2=0100$ aplicando la segunda.

Una derivación $v\longrightarrow ^*w$ es una secuencia de derivaciones directa aplicando sucesivamente producciones de un sistema. La longitud de una derivación es el número de producciones aplicadas.

Ejemplo: Sean $000\longrightarrow 010$ y $10\longrightarrow 01$ dos producciones. Desde $v=1000$ se puede derivar $w_1=0011$, es decir, $v\longrightarrow ^*w_1$ aplicando $v=1000\longrightarrow 1010\longrightarrow 0110\longrightarrow 0101\longrightarrow 0011=w_1$, o también $w_2=0001$ aplicando $v=1000\longrightarrow 0100\longrightarrow 0010\longrightarrow 0001=w_2$. En el primer caso la longitud de la derivación es 4, en el segundo caso 3.

Comentario importante: muchas de las comprobaciones en el ámbito de la teoría de los lenguajes formales se realiza mediante inducción sobre: longitud de la palabra, longitud de la derivación, (o luego también longitud del cálculo).

Dado un sistema de producciones, si sustituimos siempre la primera posibilidad a la izquierda de la palabra de partida, se llama una derivación más a la izquierda, e igual, si sustituimos siempre la primera posibilidad a la derecha de la palabra de partida, se llama una derivación más a la derecha.