Siguiente: Reglas de transformación Un nivel arriba: Gramáticas formales Anterior: Una gramática sencilla del

Otras gramáticas formales

Cadenas de 1's separadas por 0's únicos Consideremos las siguientes dos gramáticas:

$$\begin{array}{rcclrccl} a)& S &\rightarrow& 1S \vert 1T \ver... ...t 1S \vert 1 \\ &&&&&U &\rightarrow& 0U \vert 1U \end{array}$$

Como ejemplos de derivaciones de una misma palabra tenemos:

$$\begin{array}{rclrcl} \multicolumn{3}{c}{\mbox{\rm Derivaci\... ... \\ &\rightarrow& 110111 & &\rightarrow& 110111 \end{array}$$

Vemos pues que un mismo lenguaje puede ser generado por varias gramáticas.


Cualquier gramática de un lenguaje de alto nivel Como un último ejemplo de gramáticas formales mencionamos tan solo que cualquier lenguaje de programación de alto nivel está generado por una gramática formal.