Siguiente: Jerarquía de Chomsky Un nivel arriba: Introducción a la teoría Anterior: Algoritmos de Markov

Una formalización de gramáticas

Sea T un conjunto de símbolos terminales y sea V un conjunto de símbolos variables. La unión de ellos, $A = V\cup T$, es un alfabeto de gramática. A^* es el diccionario sobre A y consta de todas las palabras, de longitud finita, con símbolos en A. A⁺ coincide con A^*, salvo en que no posee a la palabra vacía, $\mbox{\it nil\/}$. Una regla de producción es un elemento del producto cartesiano $A^+ \times A^*$. Si $(\mbox{\bf a},\mbox{\bf c}) \in A^+ \times A^*$ escribimos $\mbox{\bf a} \rightarrow \mbox{\bf c}$ y decimos que $\mbox{\bf a}$ es el antecedente y $\mbox{\bf c}$ el consecuente de la regla $\mbox{\bf a} \rightarrow \mbox{\bf c}$. Sea $P\subset A^+ \times A^*$ un conjunto de reglas de producción. Sea $S \in V$ un símbolo variable distinguido, llamado inicial. El sistema G = (V, T, P, S) se dice ser una gramática formal. Las reglas de producción transforman palabras en otras:

$$\forall \mbox{\bf x} , \mbox{\bf y} \in A^* : \mbox{\bf x} \m... ... q}) \& (\mbox{\bf y} =\mbox{\bf p} \mbox{\bf c} \mbox{\bf q}).$$

La cerradura reflexivo-transitiva de la relación ``da'' define la relación de derivación

$$\forall \mbox{\bf x}, \mbox{\bf y} \in A^* : \mbox{\bf x} \mb... ...\ \mbox{\rm si}\ \ \mbox{\bf x} (\mbox{\rm da})^* \mbox{\bf y}.$$

El lenguaje generado por la gramática consta de todas las palabras que se derivan del símbolo inicial y que sólo contienen símbolos terminales:

$$\mbox{\rm Lenguaje}(G) = \{\mbox{\bf x} \in T^* \vert S\mbox{\rm deriva }\mbox{\bf x} \}.$$

Siguiente: Jerarquía de Chomsky Un nivel arriba: Introducción a la teoría Anterior: Algoritmos de Markov